组合总和II

Leetcode Link: 40. 组合总和 II - 力扣（LeetCode）

题目

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意：解集不能包含重复的组合。 

解法一

思路：一个平平无奇的回溯

本题的难点在于：集合（数组 candidates）有重复元素，但还不能有重复的组合。如何在搜索的过程中去重

求出所有元素再用 set 或者 map 去重，很容易超时 所以要在搜索的过程中就去掉重复组合。

对于本题来说，所谓去重，其实就是使用过的元素不能重复选取。

都知道组合问题可以抽象为树形结构，那么“使用过”在这个树形结构上是有两个维度的，一个维度是同一树枝上使用过，一个维度是同一树层上使用过。没有理解这两个层面上的“使用过” 是造成大家没有彻底理解去重的根本原因。

那么问题来了，对于本题来说我们是要同一树层上使用过，还是同一树枝上使用过呢？

回看一下题目，元素在同一个组合内是可以重复的，怎么重复都没事，但两个组合不能相同。

所以我们要去重的是同一树层上的“使用过”，同一树枝上的都是一个组合里的元素，不用去重。

为了理解去重我们来举一个例子 ，candidates = [1, 1, 2], target = 3，（方便起见 candidates 已经排序了）

强调一下，树层去重的话，需要对数组排序！

题解：

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        def backtracking(tar, choose):
            nonlocal path, res
            # 终止条件
            if tar < 0:
                return
 
			used = set() # 同一层不要用到相同的（去重部分）
            
            for idx, val in enumerate(choose):
                if val in used: 
                    continue  # 这里可不是 return
                else:
                    used.add(val)
                    path.append(val)
                    # 满足题目要求
                    # 排序了之后后面肯定没有了，有也是重复的，不用看了，所以return
                    if val == tar:
                        res.append(copy.deepcopy(path))
                        path.pop()
                        return 
                
                backtracking(tar-val, choose[idx+1:])
                path.pop()
 
        res = []
        path = []
        candidates.sort() # 先排序，排序好去重
        backtracking(target, candidates)
        return res
                

---

复习的时候写的代码

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        res = []
        path = []
 
        def bkt(i):
            if sum(path) == target:
                res.append(path.copy())
                return
            
            if i == len(candidates) or sum(path)>target:
                return 
            
            last_num = -float('inf')
            for next_i in range(i+1, len(candidates)):
                if candidates[next_i] != last_num: # 同一层去重
                    last_num = candidates[next_i]
                    path.append(candidates[next_i])
                    bkt(next_i)
                    path.pop()
        
        bkt(-1)
        return res

启发和联系

初次做题的时候，想到怎么做就怎么做，不要追求找到最优的代码写法或者解法。

我开始就轴，虽然我知道用sort可以去重，但感觉正确的方法是不用 sort 也能去重，最后想了半天没想出来。然后一看答案，玛勒嘎八字，就是排序后去重的…