博客

找出所有相加之和为


n


的


k


个数的组合


。


组合中只允许含有 1 – 9 的正整数，并且每种组合中不存在重复的数字。

说明：

• 所有数字都是正整数。
• 解集不能包含重复的组合。

示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]

示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]

思路：

题目看到找组合，就用回溯。

第一种版本，很麻瓜的DFS回溯。很慢只能超过 0.8%。输出会有重复所以额外加了去重的过程。

class Solution(object):
    def combinationSum3(self, k, n):
        """
        :type k: int
        :type n: int
        :rtype: List[List[int]]
        """
        if not k or not n:
            return [[]]
        
        res = []
        
        
        def dfs(k, n, tmp):
            if n == 0 and k == 0:
                res.append(tmp[:])
                return
            if k <= 0 or n <= 0:
                return
            
            for i in range(1, 10):
                if i not in tmp:
                    tmp.append(i)
                    dfs(k - 1, n - i, tmp)
                    tmp.pop()
                    
        dfs(k, n, [])
        
        ress = list()
        for i, x in enumerate(res):
            res[i] = sorted(x)
            if res[i] not in ress:
                ress.append(res[i])
        
        
        return ress

第二种版本：

dfs多加了一个变量start，代表下一次搜索的数字起点，这是用来保证不会重复并且节约了判断 i 在不在tmp 里的查找时间。

class Solution(object):
    def combinationSum3(self, k, n):
        """
        :type k: int
        :type n: int
        :rtype: List[List[int]]
        """
        if not k or not n:
            return []
        
        res = []         
        def dfs(k, n, tmp, start):
            if n == 0 and k == 0:
                res.append(tmp[:])
                return
            if k <= 0 or n <= 0:
                return
            
            for i in range(start, 10):
                tmp.append(i)
                dfs(k - 1, n - i, tmp, i + 1)
                tmp.pop()
                    
        dfs(k, n, [], 1)       
        return res

下面的写于2019年7月26日15:47:00

class Solution(object):
    def combinationSum3(self, k, n):
        """
        :type k: int
        :type n: int
        :rtype: List[List[int]]
        """
        res = []
        def dfs(start, cnt, target, tmp):
            if target < 0:
                return
            if target == 0:
                if cnt == 0:
                    res.append(tmp)
                else:
                    return
                
            for num in range(start, 10):
                visited.add(num)
                dfs(num + 1, cnt - 1, target - num, tmp + [num])
                visited.remove(num)
        visited = set()        
        dfs(1, k, n, [])
        return res