Leetcode 40:组合总和 II(最详细的解法!!!)

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

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

说明:

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

示例 1:

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

示例 2:

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

解题思路

这个问题是之前这个问题( Leetcode 39:组合总和(最详细的解法!!!))的延伸。很多人上来就修改

1
self._combinationSum2(nums, target-nums[i], i + 1, path+[nums[i]], res)# i -> i + 1

这样子的修改会出现这样的问题。对于1,71,2,5结果中会出现两次,因为我们有两个1。那要怎么做呢?最简单的做法就是增加一步检查,判断要加入的path是不是在result中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
def combinationSum2(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
result = list()
candidates.sort()
self._combinationSum2(candidates, target, 0, list(), result)
return result

def _combinationSum2(self, nums, target, index, path, res):
if target == 0 and path not in res:# add path in res
res.append(path)
return

if path and target < path[-1]:
return

for i in range(index, len(nums)):
self._combinationSum2(nums, target-nums[i], i + 1, path+[nums[i]], res)

但是这样子做很明显不是最优的解法,我们能不能优化它?我们只要在循环中添加一步控制即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
def combinationSum2(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
result = list()
candidates.sort()
self._combinationSum2(candidates, target, 0, list(), result)
return result

def _combinationSum2(self, nums, target, index, path, res):
if target == 0:
res.append(path)
return

if path and target < path[-1]:
return

for i in range(index, len(nums)):
if i > index and nums[i] == nums[i - 1]:
continue
self._combinationSum2(nums, target-nums[i], i + 1, path+[nums[i]], res)

我们要在递归前判断输入的nums[i]nums[i - 1]是不是相等,如果是的话,我们continue,否则的话,我们进入下一步递归。

同样的,对于递归可以解决的问题,我们都应该思考是不是可以通过迭代解决。这就很容易了,我们只要在之前问题的迭代基础上修改一下即可。

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
class Solution(object):
def combinationSum2(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
candidates.sort()
result = list()
stack = [(0, list(), target)]
cand_len = len(candidates)

while stack:
index, path, remain = stack.pop()
for i in range(index, cand_len):
if i > index and candidates[i] == candidates[i-1]:# add
continue

if path and remain < path[-1]:
break

if candidates[i] == remain:
result.append(path + [candidates[i]])

stack += [(i + 1, path + [candidates[i]], remain - candidates[i])]#add

return result

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!