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.

Example 1:

Input: k = 3, n = 7

Output: 

1
[[1,2,4]]

Example 2:

Input: k = 3, n = 9

Output: 

1
[[1,2,6], [1,3,5], [2,3,4]]

思路

题目需要我们找到利用k个不重复数字相加，得到数字n的所有组合。

首先想到暴力搜索，思考一下，k取1-9之间，最多会有多少种情况？答案是k取4时，C(9, 4) = 126种。k取其它数值，情况数只会比126要少。

现在的关键问题就是给定k，我们需要知道从1-9中取k个数的所有组合，再根据题意筛选所需的组合即可。

此时我们还是可以利用回溯的方法，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import copy
class Solution(object):
    def combinationSum3(self, k, n):
        """
        :type k: int
        :type n: int
        :rtype: List[List[int]]
        """
        self.digits = [1,2,3,4,5,6,7,8,9]
        self.combs = []
        self.len = 9
        result = []
        for i in range(k):
            result.append(0)
        self.comb(k, n, 0, 0, result)
        return self.combs
        
    def comb(self, k, n, curnum, curlen, result):
        if (curlen >= k):
            ans = 0
            for i in result:
                ans += i
            if (ans == n):
                tmp = copy.copy(result)
                self.combs.append(tmp)
            return
        else:
            for i in self.digits[curnum:]:
                result[curlen] = i
                self.comb(k, n, i, curlen + 1, result)

参考资料

Python- itertools中组合数的实现：
https://docs.python.org/2/library/itertools.html
组合问题的求解：
http://wuchong.me/blog/2014/07/28/permutation-and-combination-realize/
组合问题的求解：
http://blog.csdn.net/zmazon/article/details/8315418
LeetCode 77题 - Combination 解法大全：
http://www.cnblogs.com/TenosDoIt/p/3461555.html
排列组合算法：
http://www.cnblogs.com/TenosDoIt/p/3695472.html