LeetCode 组合总和(dfs)

题目

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

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

说明：

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

样例

示例 1:

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

思路

一开始是以为输出解的个数，那样的话大概率是dp问题。但是此题是输出具体解，那肯定就是搜索了。

但是，每轮dfs都从第0个元素开始搜，那么肯定会出现重复的解。那么我们只要保证，下一轮的搜索情况，必须从当前元素开始（包括当前元素）。

这样就可以避免重复解了。

代码

class Solution {
public:
    vector<int> path;
    void dfs(vector<vector<int>>& rans, vector<int>& candidates, int i, int v){
        if(v == 0){
            rans.push_back(path);
            return;
        }
        for(int ii = i; ii < candidates.size() && v >= candidates[ii]; ii++){
            path.push_back(candidates[ii]);
            dfs(rans, candidates, ii, v - candidates[ii]);  
            path.pop_back();
        }
    }


    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> rans;
        sort(candidates.begin(), candidates.end());
        dfs(rans, candidates, 0, target);
        return rans;
    }
};