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


  • 1
    S

    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
    

  • 0
    Z

    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?


Log in to reply
 

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