给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明:
- 所有数字(包括 target)都是正整数。
- 解集不能包含重复的组合。
示例 1:
输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
[7],
[2,2,3]
]
示例 2:
输入: candidates = [2,3,5], target = 8,
所求解集为:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
回溯法,递归的过程中注意剪枝。
方法一是自己写的,方法二是参考了用时最少的答案。
注意,题目还有一个没明说的隐藏要求——结果非降序排列。
- 方法一
import copy
class Solution(object):
def __init__(self):
self.res = []
self.tmp = []
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
candidates.sort()
self.getCombination(candidates, 0, len(candidates)-1, target)
return self.res
def getCombination(self, arr, istart, iend, target):
if target == 0:
t = copy.copy(self.tmp)
self.res.append(t)
return
if not arr or target < 0:
return
for index in range(istart, iend + 1):
self.tmp.append(arr[index])
cur = target - arr[index]
curi = index
while curi <= iend and arr[curi] <= cur:
curi += 1
self.getCombination(arr, index, curi-1, cur)
self.tmp.pop()
- 方法二
class Solution(object):
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
candidates.sort()
res = []
def dfs(target, path):
if target == 0:
res.append(path)
return
for x in candidates:
if x > target:
break
if path and x < path[-1]:
continue
dfs(target-x, path + [x])
dfs(target, [])
return res