39. Combination Sum这个程序为什么可以简单的通过参数i的传递就处理了重复的组合？？

Question

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

Answer 1

liuyubobobo 2018-03-25 06:48:25

在这里，combinationSum实际处理的是candidates[begin，n）的所有数据，要注意begin这个参数的用法，它影响了for循环的范围。也就是，在实际搜索的时候，一旦搜索到了一个候选数字candidates[i]，后续搜索将不再考虑i以前的所有候选数字。这步操作处理了顺序问题。你可以理解成：我们的candidates的每一个数字都有一个索引，我们实际在挑选这些数字的时候，只按照索引从小到大的顺序进行挑选，用这样的方式避免顺序重复。

这个程序在初始的时候进行了排序，使得这个过程更好理解：其实就是我们最终获得的结果，一定是升序的（严格说是不降序的）。因为我们一但选定了candidates[i]在我们的结果集中，后续搜索的数字，是在candidates[i，n）的范围里，一定大于等于candidates[i]。因此，[2，1]这样的结果不会被这个逻辑得到。因为他是降序的：）

---

最后，我的建议是：如果想真正明白程序是怎么回事，用一个小的（4，5个元素），你认为可以说明问题的测试数据，仔细的debug一遍。找个纸笔跟踪一下，一步一步的看程序是怎样执行的，每步执行数据产生了怎样的变化，为什么可以产生某种效果（避开了重复元素？一类的），和自己想的哪里不一样，自己哪里想错了或者想漏了。

这个递归函数其实只有10行而已。跟踪起来没有想象的那么复杂。我的经验是，手动跟踪一下这个函数的运行过程，可能只需要半个小时而已。将让你彻底理解整个算法的运行机理，甚至是对递归方法本身产生更深刻的理解。比对着程序生看硬想一下午要有用得多。计算机是工科，一定要动手调试：）加油！

• 提问者 慕码人1088981 #1

  我所说的参数就是combinationSum(candidates, target - candidates[i], res, combination, i)这句话中的i。
  比如给的candidates是[1 ,1, 2 ]，target是3。我在解决的时候就会出现像[1,2],[2,1]这样因为顺序不同而导致我所给出的结果是错误的。我的解决方法就是将一组和为target的数与结果中已经处理好的几组数进行比较然后丢掉这种因为顺序不同而产生的结果。
  我之所以提出这个问题，就是因为我跟着他这个程序走了几遍，发现他这个程序确实能避开我上述所出现的问题，但是我不知到该如何去理解它这种想法。

• liuyubobobo 回复 提问者 慕码人1088981 #2

  我对原答案进行了补充说明：）

• 提问者 慕码人1088981 #3

  非常感谢！

点开查看后面4条评论