题解 | #牛群喂食#

考察知识点：回溯

题目分析：

要想清楚三点：

1. 怎样处理结果会是升序的。

2. 可以不断的选取同一个元素，这该如何进行递归

3. 如何避免多个组合里元素及元素个数相同但顺序不同的情况，这种情况应该是同一种组合，不能加入到结果中。

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

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

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

所用编程语言：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, target - candidates[i], combination, res);
            combination.pop_back();
        }
    }
    vector<vector<int> > cowCombinationSum(vector<int>& candidates, int target) {
        // write code here
        sort(candidates.begin(), candidates.end());
        vector<vector<int>> res;
        vector<int> conbination;
        dfs(candidates, 0, target, conbination, res);
        return res;
    }
};