Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.The same repeated number may be chosen from candidates unlimited number of times.
Note:
- All numbers (including
target) will be positive integers. - The solution set must not contain duplicate combinations.
Example 1:
Input: candidates = [2,3,6,7] , target = 7,
A solution set is:
[
[7],
[2,2,3]
]
Example 2:
Input: candidates = [2,3,5], target = 8
A solution set is:
[
[2,2,2,2],
[2,3,3],
[3,5]
] 思路
对于在数组中进行组合查找这种类似的问题，我们可以使用递归来进行解决。因为其中同一个数字可以重复利用多次，所以对于递归的写法应该注意。解决思路主要看代码的注释。
解决代码
class Solution(object):
def combinationSum(self, nums, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
if len(nums) < 1: # nums中数目小于1时直接返回
return []
res = [] # 保存结果
nums.sort() # 排序之后可以减少递归次数
self.get_res(nums, res, 0, [],target) # 进行递归
return res def get_res(self, nums, res, index, path, target):
if target == 0: # 递归结束条件，当target等于0时，表示满足。将结果集进行添加。
return res.append(path)
if target < 0: # 递归结束条件，不满足直接进行返回。
return
for i in range(index, len(nums)): # 因为在数组中每一个数字可以多次重复利用，所以index表示从第几个元素开始进行执行。
if target < nums[index]: # 如果当前首元素大于target时，直接终止，避免不必要的递归
return
self.get_res(nums, res, i, path+[nums[i]], target-nums[i])