【LeetCode每天一题】Combination Sum(组合和)

佚名 6年前 (2019-04-12) 随笔 1151人围观抢沙发百度已收录

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:

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

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]
]

思路

    对于在数组中进行组合查找这种类似的问题，我们可以使用递归来进行解决。因为其中同一个数字可以重复利用多次，所以对于递归的写法应该注意。解决思路主要看代码的注释。
解决代码

 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 res 14     
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                 return
23             self.get_res(nums, res, i, path+[nums[i]], target-nums[i])