Leetcode 40 Combination Sum II 结果去重问题
来源：8-5 回溯法解决组合问题的优化
乐事香浓番茄味
2019-06-08
在这道题中我在最终结果中又遍历了一遍进行去重，虽然accept但是性能较差，想请老师简单提一下在递归中去重的思路，谢谢！
具体来说，leetcode 39 Combination Sum 的去重方式我已经明白，但是本题允许有重复元素，以 candidates = [2,5,2,1,2], target = 5 为例，对2进行去重时，我的程序运行结果要么没达到去重目的：出现了两个 [1,2,5]，要么把带有重复元素的合法解过滤掉了，漏掉了[1,2,2]，希望老师提供一下去重的正确思路，谢谢！
2回答
-
首先，对所有元素进行排序。
之后，在递归回溯的过程中，加入一个限制条件，不对重复元素进行搜索。对应我的题解代码：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0040-Combination-Sum-II/cpp-0040/main.cpp 37，38两行。
如果不能理解为什么这两行起到了去重目的（同时也没有遗漏），建议用一个小数据量跟踪一下整个程序，看看程序运行过程中，是如何避免重复的。你举的例子就特别好。andidates = [2,5,2,1,2], target = 5 只有5个元素，足够看出问题：）
加油！：）
012019-06-08 -
乐事香浓番茄味
提问者
2019-06-08
if(i > index && candidates[i] == candidates[i-1]) continue;
根据老师的代码，去重逻辑在这两行，这段逻辑可以这样理解：
一种是带有重复元素的合法解，比如[1,2,2]，是需要保留的，在代码中第二个2是进入下一次递归所得，此时 i = index，符合逻辑
另一种是有重复解，比如candidates = [1,2,2,5]，target = 5，没有去重会得到两个 [1,2,5]，得到第一次 [1,2,5] 之后，for 循环会继续找到第二个 2，这时如果发现重复就需要跳过
012019-06-09
相似问题