LeetCode-39-组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

所有数字（包括 target）都是正整数。
解集不能包含重复的组合。
示例 1:

输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
  [7],
  [2,2,3]
]

示例 2:

输入: candidates = [2,3,5], target = 8,
所求解集为:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

Code

//time:O(N^2)
//space:O(N)
class Solution {
private:
    vector<vector<int>> res;
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<int> temp;
        DFS(0,0,target,temp,candidates);
        return res;
    }

    void DFS(int index,int sum,int target,vector<int>& temp,vector<int>& candidates){
        if(sum==target){
            res.push_back(temp);
            return;
        }
		//由于数字可以重复使用，所以递归到下一层时，起点仍从当前index开始
        for(int i=index;i<candidates.size();i++){
            if(sum+candidates[i]<=target){
                temp.push_back(candidates[i]);
                //从index节点出发，与后面的数字进行组合
                DFS(i,sum+candidates[i],target,temp,candidates);
                temp.pop_back();
            }
        }
    }
};

Template

//关于此类问题的回溯模板
DFS(nums,ans,temp,sum,target,start){
	if(sum==target){
		ans.push_back(temp);
		return;
	}
	for(int i=start;i<nums.size();i++){
		temp.push_back(nums[i]);
		DFS(nums,ans,temp,sum+nums[i],target,start+1);
		temp.pop_back();
	}
}