[LeetCode]40. 组合总和 II(Combination Sum II)

题目描述

给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

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

说明:

  • 所有数字(包括目标数)都是正整数。
  • 解集不能包含重复的组合。

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
[1,2,2],
[5]
]

解题思路

DFS。与[LeetCode]39. 组合总和(Combination Sum)思路基本一致,增加了两个限制的条件避免重复。

代码

Python 3.6

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
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
length = len(candidates)
if length < 1:
return []

candidates.sort()
res = []
path = []
self.__dfs(0, length, candidates, target, path, res)
return res

def __dfs(self, left, right, candidates, target, path, res):
if target == 0:
res.append(path.copy())

for idx in range(left, right):
reminder = target - candidates[idx]
if reminder < 0:
break
if idx > left and candidates[idx - 1] == candidates[idx]:
# 如果在本层中已经使用了一个数字 candidates[idx-1],那么后面的相同数字不能使用
# 对于排序后的示例 [1, 1, 2, 5, 6, 7, 10],第一层第一个节点使用了 1,则该层其他节点不能再用 1
# 但第一个节点的子节点可以使用 1 之后的所有数字 [1, 2, 5, 6, 7, 10]
continue
path.append(candidates[idx])
self.__dfs(idx + 1, right, candidates, reminder, path, res)
# 注意:更深层的搜索中,要从 idx+1 处开始,因为每个数字只能使用一次
path.pop()

执行用时 : 56 ms
内存消耗 : 13.8 MB

文章目录
  1. 1. 题目描述
  2. 2. 解题思路
  3. 3. 代码
|

载入天数...载入时分秒...