leetcode40 -- Combination Sum II

leetcode40 -- Combination Sum II

题目

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

Each number in candidates may only be used once in the combination.

Note:

All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]
Example 2:

Input: candidates = [2,5,2,1,2], target = 5,
A solution set is:
[
  [1,2,2],
  [5]
]

这次和上次的不太一样了,上次的允许有重复数字的多次使用,比如一个2可以使用多次,这次加了限制,数组中的每个数只能使用一次,而且数组中是可以有重复数字出现的,这时候像上面的例子2,只能算一个。

其实这用上一题的思路就比较容易了,相当于是这一次把元素先排一个序,只需要在每次遍历之前先看一下这个元素是不是和之前的一样,如果一样就直接下一个,然后递归的时候不要再包括当前的元素了。

class Solution(object):
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        #if len(candidates) == 0:
        #    return []
        
        candidates.sort()
        res = []
        
        for i in range(len(candidates)):
            if i>0 and candidates[i]==candidates[i-1]:
                continue
            if candidates[i]>target:  # 这种情况说明candidates后面的肯定都要比target要大,所以就直接break了
                break
            if candidates[i]==target:  # 说明当前这个刚好自己可以组成一个结果. 递归的终点也是最后一个元素刚好是target了, 然后再把之前的元素给insert到其前面去.
                res.append([candidates[i]])
                break
            
            temp = self.combinationSum2(candidates[i+1:],target-candidates[i])
            for a in temp:
                a.insert(0, candidates[i])
                res.append(a)

        return res

然后python的列表其实还挺智能的,都不需要检查是否为空,所以最上面的那两行是可以注释掉的。

打赏,谢谢~~

取消

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

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

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