给定一个数组 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]
]
与“39. 组合总和”类似的思路,但是考虑在每一趟递归跳出的时候,判断下一个数字是否与当前数字一样,一样的话则跳过该数。
class Solution(object):
def combinationSum2(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
res = []
if not candidates:
return res
candidates.sort()
def dfs(path, istart, target):
if target == 0:
res.append(path)
return
else:
index = istart
while index < len(candidates):
if candidates[index] > target:
break
else:
dfs(path + [candidates[index]], index + 1, target - candidates[index])
while index < len(candidates) - 1 and candidates[index] == candidates[index + 1]:
index += 1
if index == len(candidates) - 1:
break
index += 1
dfs([], 0, target)
return res