leetcode216 -- Combination Sum III

leetcode216 -- Combination Sum III

题目


Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Note:

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

Input: k = 3, n = 7
Output: [[1,2,4]]
Example 2:

Input: k = 3, n = 9
Output: [[1,2,6], [1,3,5], [2,3,4]]

这个题的意思现在变了,即现在要用1到9这9个数,返回和为n的并且长度为k的所有的组合

解答

这个题我还是应用第一道题的想法,即先把所有的组合都找出来,然后过滤出来长度为k的组合。其实也可以在里面加一个判断直接弄掉,也少了很多运算,刚开始没有看到是用数字1-9,


class Solution(object):
    def combinationSum3(self, k, n):
        """
        :type k: int
        :type n: int
        :rtype: List[List[int]]
        """
        if k<=0 or n<=0:
            return []
        
        # temp = self.helper(range(1, n+1), n)
        temp = self.helper(range(1,10), n)
        res = []
        for x in temp:
            if len(x)==k:
                res.append(x)
                
        return res
        
        
        
    def helper(self, candidates, target):
        res = []
        
        for i in range(len(candidates)):
            if candidates[i]>target:
                break
            if candidates[i] == target:
                res.append([candidates[i]])
                break
                
            temp = self.helper(candidates[i+1:], target-candidates[i])
            for a in temp:
                a.insert(0, candidates[i])
                res.append(a)
                
        return res
    
            

这个题会的话,那么k不固定的时候也会了。

后来再想想在中间加上判断实际上是不太对的,因为中间的结果还要加上以前的结果才能是最终的结果。还是在最终的结果里面加上判断比较好。

打赏,谢谢~~

取消

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

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

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