题解 | #牛群分组II#

考察知识点：回溯

题目分析：

和上一题类似，改变的地方就是由“同一元素能够被选取多次”，改变成了“同一元素只能被选取一次”。只需要将在选取元素遍历数组时遍历的起点更改一下即可。

首先，优选条件是数值较小的先选，那么由于原数组可能是无序的，我们可以将数组按照升序排序。这样数组的循序恰好就满足优选条件。

那么，既然我们的结果是升序的，也就是说先选取的数比较小，后面的数一定大于等于这个数。发现在选取元素遍历数组时可以控制遍历的起点。如果我们选取了第i个数，下一层遍历时从第i + 1个数开始，那么就可以保证一个元素只会被选取一次，并且保证了左边的数始终小于等于右边。

发现其实结果中的各个数组也是一个升序的数组，这就保证了加入到结果集中的组合的唯一性。

所用编程语言：C++

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param candidates int整型vector 
     * @param target int整型 
     * @return int整型vector<vector<>>
     */
    void dfs(vector<int> &candidates, int start, int target, vector<int> &combination, vector<vector<int>> &res) {
        if (target == 0) {
            res.push_back(combination);
            return;
        }
        if (target < 0) return;
        int size = candidates.size();
        for (int i = start; i < size; i++) {
            combination.push_back(candidates[i]);
            dfs(candidates, i + 1, target - candidates[i], combination, res);
            combination.pop_back();
        }
    }
    vector<vector<int> > cowCombinationSum2(vector<int>& candidates, int target) {
        // write code here
        vector<int> combination;
        vector<vector<int>> res;
        dfs(candidates, 0, target, combination, res);
        return res;
    }
};