leetcode40.组合总和 II

40. 组合总和 II

中等（选与不选）

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

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

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

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]

代码一：

超出时间限制 172 / 176 个通过的测试用例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        ans = []
        candidates.sort()
        def func1(temp,pos,k):
            nonlocal ans
            if k == 0:
                if temp not in ans:
                    ans.append(temp)
                return
            if pos >= len(candidates):
                return 
            if candidates[pos] > k:
                return
            lst = temp[:]
            lst.append(candidates[pos])
            func1(lst,pos+1,k-candidates[pos])
            func1(temp,pos+1,k)
        func1([],0,target)
        return ans

思路：

数组排序，减少判断次数。 pos 从小到大依次遍历数组的位置，如果当前位置的值超过需要添加的值，返回空；否则考虑添加与否两种情况。数组 temp 元素之和满足条件时，如果 ans 中没有添加过，添加到 ans 中。

代码二：代码一优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        ans = []
        candidates.sort()
        temp = []  #不作为传参
        def func1(pos,k):
            if k == 0:
                ans.append(temp[:])  #注意这里只能是副本，不能是引用
                return
            if pos >= len(candidates):
                return 
            if candidates[pos] > k:
                return
            temp.append(candidates[pos])
            func1(pos+1,k-candidates[pos])
            temp.pop()   #回溯到添加元素前的情况
            # 避免添加重复数组
            for i in range(pos+1,len(candidates)):
                if candidates[i] != candidates[pos]:
                    func1(i,k)
                    return
        func1(0,target)
        return ans

思路：

代码二是代码一的优化，临时数组temp不作为参数传递给函数，当然，每次添加元素后还需要回溯到添加前的状态来考虑不添加当前元素的情况。为避免添加重复的数组，还需要跳过元素相同的位置。

代码三：来自灵神

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        n = len(candidates)
        ans = []
        path = []

        def dfs(i: int, left: int) -> None:
            # 所选元素之和恰好等于 target
            if left == 0:
                ans.append(path.copy())  # 也可以写 path[:]
                return

            # 在 [i,n-1] 中选一个 candidates[j]
            # 注意选 candidates[j] 意味着 [i,j-1] 中的数都没有选
            for j in range(i, n):
                # 后面的数不需要选了，元素之和必然无法恰好等于 target
                if left < candidates[j]:
                    break
                # 考虑选 candidates[j]
                # 如果 j>i，说明 candidates[j-1] 没有选 
                # 同方法一，所有等于 candidates[j-1] 的数都不选
                if j > i and candidates[j] == candidates[j - 1]:
                    continue
                path.append(candidates[j])
                dfs(j + 1, left - candidates[j])
                path.pop()  # 恢复现场

        dfs(0, target)
        return ans