组合总和

Question

给定一组候选数字 (C) 和一个目标数字 (T)，找出 C 中候选数字总和为 T 的所有唯一组合。

相同的重复数字可以从 C 中选择无限次。

All numbers (including target) will be positive integers.
Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
The combinations themselves must be sorted in ascending order.
CombinationA > CombinationB iff (a1 > b1) OR (a1 = b1 AND a2 > b2) OR … (a1 = b1 AND a2 = b2 AND … ai = bi AND ai+1 > bi+1)
The solution set must not contain duplicate combinations.

例如，给定候选集 2,3,6,7 和目标 7，一个解集是：

[2, 2, 3] [7]

解决方案代码为：

class Solution {
    public:

    void doWork(vector<int> &candidates, int index, vector<int> &current, int currentSum, int target, vector<vector<int> > &ans) {
        if (currentSum > target) {
            return;
        }
        if (currentSum == target) {
            ans.push_back(current);
            return;
        }
        for (int i = index; i < candidates.size(); i++) {
            current.push_back(candidates[i]);
            currentSum += candidates[i];

            doWork(candidates, i, current, currentSum, target, ans);

            current.pop_back();
            currentSum -= candidates[i];
        }

    }

    vector<vector<int>> combinationSum(vector<int> &candidates, int target) {
        vector<int> current; 
        vector<vector<int> > ans;
        sort(candidates.begin(), candidates.end());
        vector<int> uniqueCandidates;
        for (int i = 0; i < candidates.size(); i++) {
            if (i == 0 || candidates[i] != candidates[i-1]) {
                uniqueCandidates.push_back(candidates[i]);
            }
        }
        doWork(uniqueCandidates, 0, current, 0, target, ans); 
        return ans;
    }
};

现在，虽然我可以通过举个例子来理解解决方案，但我自己怎么能想出这样的解决方案。主要工作在这个函数中进行：

    for (int i = index; i < candidates.size(); i++) {
        current.push_back(candidates[i]);
        currentSum += candidates[i];

        doWork(candidates, i, current, currentSum, target, ans);

        current.pop_back();
        currentSum -= candidates[i];
    }

请告诉我如何理解上面的代码以及如何思考该解决方案。我可以解决基本的递归问题，但这些看起来遥不可及。感谢您的宝贵时间。

Answer 1

所以代码基本上做的是：

按升序对给定的一组数字进行排序。
从集合中删除重复项。
对于集合中的每个数字：
- 继续添加相同的数字，直到总和大于或等于目标。
- 如果相等，保存组合。
- 如果比较大，去掉最后加的数（回到上一步），开始把集合中的下一个数加到总和。

为了理解递归，我喜欢从非常简单的案例开始。让我们举个例子： Candidates: { 2, 2, 1 } Target: 4

排序并删除重复项会将集合更改为 { 1, 2 }。递归顺序为：

总和=1；
- 总和=1+1；
  - 总和=1+1+1；
    - 总和 = 1 + 1 + 1 + 1; （同target，保存组合）
    - 总和 = 1 + 1 + 1 + 2；（大于目标，没有更多的数字添加）
  - 总和=1+1+2；（保存组合，不再添加数字）
- 总和=1+2；
  - 总和=1+2+2；（更大，没有更多）
总和=2；
- 总和=2+2；（保存，这是最后一次递归）

组合总和

Combination Sum

c++

recursion

combinations

backtracking