[LeetCode] Challenge log 216

Posted on |
216. Combination Sum III

Analysis:

  1. Same as 39 & 49.
  2. Keep the numbers in returned set in accending order to avoid duplicates.
  3. trim the tree by judging if a number is greater than target
  4. take care of the boundary: n==0, k ==0

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:

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

Example 2:

1
2
Input: k = 3, n = 9
Output: [[1,2,6], [1,3,5], [2,3,4]]
Soulution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def combinationSum3(self, k, n):
        """
        :type k: int
        :type n: int
        :rtype: List[List[int]]
        """
        res = []
        def dfs(k, n, st):
            if n == 0 and  k == 0: 
                return res.append(st)
            elif n == 0 or k == 0: 
                return
            for i in range(1, 10):
                if st and i <= st[-1]: continue
                if i > n: break
                dfs(k-1, n-i, st + [i])
        dfs(k, n , [])
        return res
0%