大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目考察的知识点

本题考察组合问题的解决方法，需要找出数组中可以使编号和为目标数 target 的所有不同组合。

题目解答方法的文字分析

我们可以使用回溯法（Backtracking）来解决这个问题。回溯法是一种穷举搜索算法，它通过逐步构建解决方案，并在构建的过程中进行剪枝，以避免无效的搜索路径，从而找到所有符合条件的解。

具体步骤如下：

  1. 首先，对数组 candidates 进行排序，这样可以方便后续剪枝操作。
  2. 创建一个辅助函数 backtrack，该函数用于在数组 candidates 中搜索所有符合条件的组合。函数参数包括当前搜索位置 start、当前已选择的组合 current_combination 和当前组合的编号和 current_sum。
  3. 在 backtrack 函数中，首先判断如果 current_sum 等于 target，说明找到了一个符合条件的组合，将其加入结果集中。
  4. 否则，从 start 位置开始遍历 candidates 数组，并进行回溯：如果当前元素加上 current_sum 小于等于 target，说明可以选择该元素，将其加入 current_combination 中，并调用 backtrack 函数继续搜索下一个位置。在回溯完成后，要将刚刚选择的元素从 current_combination 中移除，以便尝试其他选择。在遍历 candidates 数组时，要注意跳过重复的元素，避免出现重复的组合。

本题解析所用的编程语言

C++

完整且正确的编程代码

#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    /**
     * 在数组 candidates 中找出所有符合条件的组合，使得组合中的元素之和等于目标数 target。
     * 
     * @param candidates int整型vector，表示每头牛的编号
     * @param target int整型，表示每组牛的编号之和
     * @return int整型vector<vector<>>，返回所有符合条件的组合列表
     */
    vector<vector<int>> cowCombinationSum2(vector<int>& candidates, int target) {
        vector<vector<int>> result;            // 存放所有符合条件的组合列表
        vector<int> current_combination;       // 存放当前正在构建的组合
        sort(candidates.begin(), candidates.end()); // 对数组进行排序，方便后续剪枝

        // 调用回溯函数开始搜索
        backtrack(candidates, 0, target, current_combination, result);
        return result;
    }

private:
    /**
     * 回溯函数，在数组 candidates 中搜索所有符合条件的组合，并将其加入结果集中。
     *
     * @param candidates int整型vector，表示每头牛的编号
     * @param start int整型，表示当前搜索的起始位置
     * @param target int整型，表示每组牛的编号之和
     * @param current_combination int整型vector，表示当前正在构建的组合
     * @param result int整型vector<vector<>>，存放所有符合条件的组合列表
     */
    void backtrack(vector<int>& candidates, int start, int target, vector<int>& current_combination, vector<vector<int>>& result) {
        // 如果当前组合的编号之和等于目标数 target，说明找到了一个符合条件的组合，将其加入结果集中
        if (target == 0) {
            result.push_back(current_combination);
            return;
        }

        // 从 start 位置开始遍历 candidates 数组，并进行回溯
        for (int i = start; i < candidates.size(); i++) {
            if (i > start && candidates[i] == candidates[i - 1]) {
                // 跳过重复元素，避免重复组合
                continue;
            }

            if (candidates[i] <= target) {
                // 如果当前元素加上 current_sum 小于等于 target，说明可以选择该元素
                current_combination.push_back(candidates[i]);
                // 继续搜索下一个位置，更新 target 值为 target - candidates[i]
                backtrack(candidates, i + 1, target - candidates[i], current_combination, result);
                // 回溯完成后，将刚刚选择的元素从 current_combination 中移除，以便尝试其他选择
                current_combination.pop_back();
            }
        }
    }
};

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！