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

题目考察的知识点

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

题目解答方法的文字分析

这道题与之前的题目有一点不同，这次每个数字可以无限制重复被选取。我们仍然可以使用回溯法来解决，但在回溯的过程中，我们不再需要跳过重复的元素，而是继续考虑当前元素。

具体步骤如下：

  1. 创建一个辅助函数 backtrack，该函数用于在数组 candidates 中搜索所有符合条件的组合。函数参数包括当前搜索位置 start、当前已选择的组合 current_combination 和当前组合的食物总量 current_sum。
  2. 在 backtrack 函数中，首先判断如果 current_sum 等于 target，说明找到了一个符合条件的组合，将其加入结果集中。
  3. 否则，从 start 位置开始遍历 candidates 数组，并进行回溯：如果当前元素加上 current_sum 小于等于 target，说明可以选择该元素，将其加入 current_combination 中，并继续调用 backtrack 函数以考虑继续选择当前元素。在回溯完成后，要将刚刚选择的元素从 current_combination 中移除，以便尝试其他选择。在遍历 candidates 数组时，由于每个数字可以无限制重复被选取，因此下一次的起始位置还是当前位置，继续考虑当前元素的选择。

本题解析所用的编程语言

C++

完整且正确的编程代码

#include <vector>

using namespace std;

class Solution {
public:
    /**
     * 在数组 candidates 中找出所有符合条件的组合，使得组合中的食物总量等于目标数 target。
     * 
     * @param candidates int整型vector，表示每头牛的食物需求
     * @param target int整型，表示农场主人需要喂食的总量
     * @return int整型vector<vector<>>，返回所有符合条件的组合列表
     */
    vector<vector<int>> cowCombinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> result;            // 存放所有符合条件的组合列表
        vector<int> current_combination;       // 存放当前正在构建的组合

        // 调用回溯函数开始搜索
        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 (candidates[i] <= target) {
                // 如果当前元素的食物需求小于等于目标数 target，说明可以选择该元素
                current_combination.push_back(candidates[i]);
                // 继续搜索下一个位置，更新 target 值为 target - candidates[i]
                backtrack(candidates, i, target - candidates[i], current_combination, result); // 注意这里传入的是 i，而不是 i+1
                // 回溯完成后，将刚刚选择的元素从 current_combination 中移除，以便尝试其他选择
                current_combination.pop_back();
            }
        }
    }
};

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