216 Combination Sum III

用K个1-9的数字组成N, 使用backtracking回溯方法来解。

class Solution(object):
    def __init__(self):
        self.ans = []

    def combinationSum3(self, k, n):
        """
        :type k: int
        :type n: int
        :rtype: List[List[int]]
        """
        candidates = [i for i in range(10)]
        length = len(candidates)

        def dfs(vis, index, cur_sum, cur_num, cur):
            if cur_sum == n and cur_num == k:
                self.ans.append(cur)
                return

            if cur_sum > n:
                return

            for i in range(index, length):
                if vis[i] == False:
                    vis[i] = True
                    new_cur = cur[::]
                    new_cur.append(candidates[i])
                    dfs(vis, i, cur_sum + candidates[i], cur_num + 1, new_cur)
                    vis[i] = False

        dfs([False for i in range(10)], 1, 0, 0, [])
        return self.ans