[ LeetCode ]#39. Combination Sum(组合求和C++ & Python)

题目：39. Combination Sum

Given a set of candidate numbers (

candidates

) (without duplicates) and a target number (

target

), find all unique combinations in 

candidates

 where the candidate numbers sums to 

target

.

The same repeated number may be chosen from 

candidates

 unlimited number of times.

Note:

• All numbers (including 

  target

  ) will be positive integers.
• The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
  [7],
  [2,2,3]
]
           

Example 2:

Input: candidates = [2,3,5], target = 8,
A solution set is:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]
           

题意：

给定一个正整数数列不包含重复的值和一个整数target。求出所给数列中任意元素之和为target的所有不重复组合，组合中数列中的值可以重复出现，比如example1：8=2+2+2+2.

分析：

使用回漱可解决此问题，即从数列的起始部分开始，每次将当前的值记入求和数列中（数列中所有元素之和记为sum），并判断当前target与sum的差值，如果插值为0，则说明当前数列中的值可以累加等到target，若大于0，则说明当前数列中的数值之和还不足target 需要继续添加元素，若小于0，则说明当前数列中的元素之和已经大于target了，这种组合一定没有解，可以结束此次查找。

Code & C++

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> tmp;
    void getSum(vector<int>& candidates, int idx, int target){
        if(target==0){
            ans.push_back(tmp);
            return ;
        }else if(target<0){
            return ;
        }
        for(int i=idx; i<candidates.size();i++){
            if(candidates[i]<=target){
                tmp.push_back(candidates[i]);
                getSum(candidates,i, target-candidates[i]);
                tmp.pop_back();
            }
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
     	vector<int> res;
        sort(candidates.begin(),candidates.end());
        getSum(candidates,0,target);
        return ans;
    }
};
           

Result:

Runtime: 12 ms, faster than 100.00% of C++ online submissions for Combination Sum.

Memory Usage: 10.8 MB, less than 52.94% of C++ online submissions forCombination Sum.

Code & Python

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        ans = []
        candidates.sort()
        def getSum(tmp: 'List[int]', idx: 'int', target: 'int'):
            if target == 0:
                ans.append(tmp)
                return
            elif target < 0:
                return
            for i in range(idx, len(candidates)):
                if candidates[i] <= target:
                    getSum(tmp + [candidates[i]], i, target - candidates[i])
        getSum([], 0, target)
        return ans
           

Result:

Runtime: 88 ms, faster than 62.43% of Python3 online submissions for Combination Sum.

Memory Usage: 13.1 MB, less than 5.14% of Python3 online submissions forCombination Sum.