# DFS solution for Combination Sum I II III with C++ and python

• ## for Combination Sum

##### c++ solution:
``````class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> ret;
vector<int> temp;
sort(candidates.begin(),candidates.end());
findCbSum(candidates,target,0,temp,ret);
return ret;
}
void findCbSum(vector<int>& candidates,int target,int index,vector<int>& result,vector<vector<int>>& results)
{
if(target==0)   {results.push_back(result);}
else if(target<0 or candidates[index]>target)    {;}
else
{
for(int i=index;i<candidates.size();i++)
{
result.push_back(candidates[i]);
findCbSum(candidates,target-candidates[i],i,result,results);
result.pop_back();
}
}
}
};
``````
##### my python solution:
``````class Solution(object):
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
def findCbSum(candidates,target,result,results):
if target == 0: results.append(result)
elif target < 0 or candidates[0] > target: return
else:
for i in range(len(candidates)):
findCbSum(candidates[i:],target-candidates[i],result+[candidates[i]],results)
ret = []
findCbSum(sorted(candidates),target,[],ret)
return ret
``````

## for Combination Sum II

##### c++ solution
``````class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<vector<int>> ret;
vector<int> temp;
sort(candidates.begin(),candidates.end());
findCbSum(candidates,target,0,temp,ret);
return ret;
}
void findCbSum(vector<int>& candidates,int target,int index,vector<int>& result,vector<vector<int>>& results)
{
if(target==0)   {results.push_back(result);}
else if(target<0 or candidates[index]>target)    {;}
else
{
for(int i=index;i<candidates.size();i++)
{
result.push_back(candidates[i]);
findCbSum(candidates,target-candidates[i],i+1,result,results);
result.pop_back();
while(i<candidates.size()-1 && candidates[i]==candidates[i+1]) i++;
}
}
}
};
``````
##### python solution
``````class Solution(object):
def combinationSum2(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
def findCbSum(candidates,target,result,results):
if target==0: results.append(result)
if target <0 or not candidates or candidates[0] > target: return
else:
for i in range(len(candidates)):
if i>0 and candidates[i]==candidates[i-1]: continue
findCbSum(candidates[i+1:],target-candidates[i],result+[candidates[i]],results)

ret = []
findCbSum(sorted(candidates),target,[],ret)
return ret
``````

## for Combination Sum III

##### python solution
``````class Solution(object):
def combinationSum3(self, k, n):
"""
:type k: int
:type n: int
:rtype: List[List[int]]
"""
def findCbSum(index,k,n,result,results):
if k==0 and n==0: results.append(result)
elif k==0 or n<=0 : return
elif k > 0 and n > 0:
for i in range(index,10):
findCbSum(i+1,k-1,n-i,result+[i],results)
ret = []
if 9*k>n:
findCbSum(1,k,n,[],ret)
return ret
``````

• Thanks for sharing!

I am wondering why you copy the list in Python by passing result+[candidates[i]] instead of using a shared list by calling append/pop. List copying looks significant slower than your C++ based solution, but in reality it doesn't. Why doesn't it hurt performance much?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.