Leetcode 40 Combination Sum II 结果去重问题

Question

在这道题中我在最终结果中又遍历了一遍进行去重，虽然accept但是性能较差，想请老师简单提一下在递归中去重的思路，谢谢！

具体来说，leetcode 39 Combination Sum 的去重方式我已经明白，但是本题允许有重复元素，以 candidates = [2,5,2,1,2], target = 5 为例，对2进行去重时，我的程序运行结果要么没达到去重目的：出现了两个 [1,2,5]，要么把带有重复元素的合法解过滤掉了，漏掉了[1,2,2]，希望老师提供一下去重的正确思路，谢谢！

Answer 1

liuyubobobo 2019-06-08 18:41:34

首先，对所有元素进行排序。

之后，在递归回溯的过程中，加入一个限制条件，不对重复元素进行搜索。对应我的题解代码：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个元素，足够看出问题：）

加油！：）

• 提问者 乐事香浓番茄味 #1

  非常感谢！

Answer 2

提问者 乐事香浓番茄味 2019-06-08 21:02:32

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，这时如果发现重复就需要跳过

• liuyubobobo #1

  大赞！继续加油！：）