leetcode39 -- Combination Sum

leetcode39 -- Combination Sum

题目


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

理解题意: 这道题的意思是给定一个目标target, 给定一个数组,需要返回数组中的组合,使得每个组合的和刚好是target,数组中的数字甚至可以重复使用。

解答

方法是用递归, 拿题目中的[2,3,5],target=8来理解,刚开始start=0,out先把2给append起来,然后递归地进入

combinationSumDFS(candidates, 6, 0, [2], [])

这个进去之后,会再进入combinationSumDFS(candidates, 4, 0, [2,2],[])

然后再进入combinationSumDFS(candidates, 2, 0, [2,2,2], []),

然后再进入combinationSumDFS(candidates, 0, 0, [2,2,2,2], []) 从而res.append([2,2,2,2]).然后进入out又变成了[2,2,2] 然后i=1,out变成[2,2,2,3] 进入

combinationSumDFS(candidates, -1, 1, [2,2,2,3], [[2,2,2,2]]) 但是这四个不对,所以直接返回,所以一直这样下去的话,就能把所有的都能够找到,这里有个很关键的地方即递归的时候传入的参数start是从i开始传入的,而不是i+1,这就意味着允许有重复的出现。

代码如下

class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        res = []
        self.combinationSumDFS(candidates, target, 0, [], res)
        return res
    
    def combinationSumDFS(self, candidates, target, start, out, res):
        if target<0:
            return
        if target==0:
            res.append(out[:])  # 注意这里append的是copy的,不然后面因为有删除操作的话,又都删除了.
            return 
        for i in range(start, len(candidates)):
            out.append(candidates[i])  # 把第一个元素拿起来之后,剩下的就是递归的子问题了,而且候选的元素不变,start也是从当前的这个元素i开始的。
            self.combinationSumDFS(candidates, target-candidates[i], i, out, res)
            del(out[-1])  # 递归完了之后无论candidates[i]合不合适都要把它去掉进行下一次的尝试。

也可以用下面的办法


class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        res = []
        candidates.sort()
        for i in range(len(candidates)):
            if candidates[i]>target:
                break
            if candidates[i]==target:
                res.append([candidates[i]])
                break
            later = candidates[i:]
            temp = self.combinationSum(later, target-candidates[i])
            # temp [[]]
            for a in temp:
                a.insert(0, candidates[i])
                res.append(a)
                
        return res

即不借助于其它的函数。相当于是先对数组排一个序,然后从小到大遍历每一个数字,如果当前的数字比target要大,那么直接break,因为后面也不可能了,如果当前的数字刚好等于target的,那就把这个结果放进去,如果当前的数字比target要小的话,那就可以转化为一个子问题,其中子问题的search对象是candidates[i:] target是target-candidates[i]. 然后将递归得到的结果加上当前的这个元素candidates[i],然后返回即可。

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦