题解 | #牛群分组II#

考察的知识点：回溯；

解答方法分析：

1. 对输入的数组 candidates 进行排序，这样可以保证在回溯过程中，数字组合的升序排列。
2. 定义一个辅助函数 backtrack，在其中进行回溯操作。
3. 在回溯函数中，首先判断当前和是否等于目标整数 target，如果相等，则将当前组合添加到结果列表 res 中。
4. 然后，从当前数字的索引开始循环遍历数组，判断当前数字是否已经被选取，如果已经被选取，则跳过。如果当前数字大于剩余的目标整数，说明后的数字也不可能满足条件，可以进行剪枝操作，直接返回。
5. 如果以上条件都不满足，将当前数字加入到组合中，当前和，并将当前数字标记为已选取。然后，递归调用回溯函数，传递更新后的参数。
6. 递归结束后，将当前数字从组合中移除，并将当前数字标记为未选取，以便进行下一次迭代。
7. 最后，返回结果列表 res。

所用编程语言：C++；

完整编程代码：↓

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