题解 | #牛群喂食#

考察的知识点：回溯；

解答方法分析：

1. 对给定的candidates数组进行排序，以便后续操作。这是为了确保生成的组合是按照升序排列的，避免重复的组合。
2. 创建一个空的结果二维数组res，用于保存符合要求的所有组合。
3. 创建一个空的一维数组combination，用于保存当前生成的组合。
4. 调用递归辅助函数backtracking，并传入排序后的candidates数组、目标数target、开始位置start、组合数组combination、结果数组res。
5. 在backtracking函数中，首先判断如果target已经减到0，说明找到了一个符合要求的组合，将其加入res，然后返回。
6. 接下来使用一个循环遍历从开始位置start到数组末尾的每个数字：如果当前数字candidates[i]大于目标值target，说明后面的数字都会大于target，直接返回。将当前数字candidates[i]加入组合数组combination。递归调用backtracking函数，传入更新后的目标数target - candidates[i]、当前位置i、组合数组combination和结果数组res。回溯，将刚刚加入的数字从组合数组combination中取出，继续下一轮的选择。
7. 最后，将结果数组res返回。

所用编程语言：C++；

完整编程代码：↓

class Solution {
  public:
    vector<vector<int> > cowCombinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> res;
        vector<int> combination;
        sort(candidates.begin(), candidates.end());
        backtracking(candidates, target, 0, combination, res);
        return res;
    }
  private:
    void backtracking(vector<int>& candidates, int target, int start,
                      vector<int>& combination, vector<vector<int>>& res) {
        if (target == 0) {
            res.push_back(combination);
            return;
        }
        for (int i = start; i < candidates.size(); i++) {
            if (candidates[i] > target) {
                return;
            }
            combination.push_back(candidates[i]);
            backtracking(candidates, target - candidates[i], i, combination, res);
            combination.pop_back();
        }
    }
};