卖萌的弱渣

I am stupid, I am hungry.

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.

Example 1:

1
2
3
4
5

Input: k = 3, n = 7

Output:

[[1,2,4]]

Example 2:

1
2
3
4
5

Input: k = 3, n = 9

Output:

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

Solution

(Combination-Sum3.py) download
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

class Solution(object):
    def combinationSum3(self, k, n):
        """
        :type k: int
        :type n: int
        :rtype: List[List[int]]
        """
        ret = []

        self.findSol(k,n,ret,[],1)
        return ret

    def findSol(self,k,n,ret,tmp,val):
        if n < 0:
            return
        if k == 0:
            if n != 0:
                return
            else:
                ret.append(tmp[:])
                return
        for i in range(val,10):
            tmp.append(i)
            self.findSol(k-1,n-i,ret,tmp,i+1)
            tmp.pop()
        return