39. Combination Sum这个程序为什么可以简单的通过参数i的传递就处理了重复的组合？？
来源：8-5 回溯法解决组合问题的优化
慕码人1088981
2018-03-24
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();
}
}
};1回答
-
在这里，combinationSum实际处理的是candidates[begin，n）的所有数据，要注意begin这个参数的用法，它影响了for循环的范围。也就是，在实际搜索的时候，一旦搜索到了一个候选数字candidates[i]，后续搜索将不再考虑i以前的所有候选数字。这步操作处理了顺序问题。你可以理解成：我们的candidates的每一个数字都有一个索引，我们实际在挑选这些数字的时候，只按照索引从小到大的顺序进行挑选，用这样的方式避免顺序重复。
这个程序在初始的时候进行了排序，使得这个过程更好理解：其实就是我们最终获得的结果，一定是升序的（严格说是不降序的）。因为我们一但选定了candidates[i]在我们的结果集中，后续搜索的数字，是在candidates[i，n）的范围里，一定大于等于candidates[i]。因此，[2，1]这样的结果不会被这个逻辑得到。因为他是降序的：）
---
最后，我的建议是：如果想真正明白程序是怎么回事，用一个小的（4，5个元素），你认为可以说明问题的测试数据，仔细的debug一遍。找个纸笔跟踪一下，一步一步的看程序是怎样执行的，每步执行数据产生了怎样的变化，为什么可以产生某种效果（避开了重复元素？一类的），和自己想的哪里不一样，自己哪里想错了或者想漏了。
这个递归函数其实只有10行而已。跟踪起来没有想象的那么复杂。我的经验是，手动跟踪一下这个函数的运行过程，可能只需要半个小时而已。将让你彻底理解整个算法的运行机理，甚至是对递归方法本身产生更深刻的理解。比对着程序生看硬想一下午要有用得多。计算机是工科，一定要动手调试：）加油！
072018-03-29
相似问题