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 = 8A solution set is:[ [2,2,2,2], [2,3,3], [3,5]] 思路
对于在数组中进行组合查找这种类似的问题，我们可以使用递归来进行解决。因为其中同一个数字可以重复利用多次，所以对于递归的写法应该注意。解决思路主要看代码的注释。 解决代码
1 class Solution(object): 2 def combinationSum(self, nums, target): 3 """ 4 :type candidates: List[int] 5 :type target: int 6 :rtype: List[List[int]] 7 """ 8 if len(nums) < 1: # nums中数目小于1时直接返回 9 return []10 res = [] # 保存结果11 nums.sort() # 排序之后可以减少递归次数12 self.get_res(nums, res, 0, [],target) # 进行递归13 return res14 15 def get_res(self, nums, res, index, path, target):16 if target == 0: # 递归结束条件，当target等于0时，表示满足。将结果集进行添加。17 return res.append(path)18 if target < 0: # 递归结束条件，不满足直接进行返回。19 return 20 for i in range(index, len(nums)): # 因为在数组中每一个数字可以多次重复利用，所以index表示从第几个元素开始进行执行。21 if target < nums[index]: # 如果当前首元素大于target时，直接终止，避免不必要的递归22 return23 self.get_res(nums, res, i, path+[nums[i]], target-nums[i])