首页 > itarticle > leetcode_combination sum iii

leetcode_combination sum iii

admin 11月 13, 2020 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.
（从1-9中选取k个数的和为n）

Note:

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

Example:

1. 回溯法

class :
    def back_tracking(self, list, i, k, count):
        if count == 0 and k == 0:
            self.results.append(list)
        
        for j in range(i, 10):
            self.back_tracking(list+[j], j+1, k-1, count-j)
        
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        self.results = []
        self.back_tracking([], 1, k, n)
        
        return self.results