组合总和

给你一个无重复元素的整数数组candidates和一个目标整数target，找出candidates中可以使数字和为目标数target的所有 不同组合，并以列表形式返回。你可以按任意顺序返回这些组合。

对于candidates中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为target的不同组合数少于150个。

提示：

• 1 <= candidates.length <= 30
• 1 <= candidates[i] <= 200
• candidate中的每个元素都互不相同
• 1 <= target <= 500

39.组合总和

我真是奇了怪了题目描述第二段少了开头的“对于”俩字就全乱了是什么鬼bug

很明显的回溯题，对于每一个数字有选择和不选择的方案。所以回溯的时候有一个直接选择下一个数字的递归，还有一个选择当前数字的递归。后一个递归的前后给临时答案放入和弹出数据。

小黎本来对数组弄了个排序，但是好像除了拖慢运行效率并没有啥用。也就是对于无解的情况有点用吧，但是测试样例中无解的比重应该并不大，所以看起来没啥用。

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        // sort(candidates.begin(), candidates.end());
        vector<vector<int>> ans;
        // if(candidates[0] > target){
        //     return ans;
        // }
        vector<int> temp;
        backTrack(candidates, ans, temp, 0, target);
        return ans;
    }
    void backTrack(vector<int>& candidates, vector<vector<int>>& ans, vector<int>& temp, int idx, int target){
        if(target == 0){
            ans.push_back(temp);
            return;
        }
        if(target < 0 || idx >= candidates.size()){
            return;
        }
        backTrack(candidates, ans, temp, idx + 1, target);

        temp.push_back(candidates[idx]);
        backTrack(candidates, ans, temp, idx, target - candidates[idx]);
        temp.pop_back();
    }
};

不过对于组合总和II来说，排序就是必要的。因为此时包含重复的数字，且每个数字在每个组合中只可以使用一次，明显需要用到排序。

而且这个地方每个数字只能使用一次，所以不能像这题一样回溯，需要有一个for循环来选取数字。

class Solution {
private:
    vector<int> candidates;
    vector<vector<int>> res;
    vector<int> path;
public:
    void DFS(int start, int target) {
        if (target == 0) {
            res.push_back(path);
            return;
        }

        for (int i = start; i < candidates.size() && target - candidates[i] >= 0; i++) {
            if (i > start && candidates[i] == candidates[i - 1])
                continue;
            path.push_back(candidates[i]);
            // 元素不可重复利用，使用下一个即i+1
            DFS(i + 1, target - candidates[i]);
            path.pop_back();
        }
    }

    vector<vector<int>> combinationSum2(vector<int> &candidates, int target) {
        sort(candidates.begin(), candidates.end());
        this->candidates = candidates;
        DFS(0, target);
        return res;
    }
};

（突然发现自己以前写过这个题目，偷个懒