[ 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.