Problem of The Day: Combination Sum III

Problem Statement

leetcode problem link

Back track [Accepted]

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        res = []
        def backtrack(start, remain_k, curr, curr_sum):
            if remain_k == 0:
                if curr_sum == n:
                    res.append(curr[:])
                return
            for i in range(start, 10):
                if curr_sum + i <= n:
                    curr.append(i)
                    backtrack(i + 1, remain_k - 1, curr, curr_sum + i)
                    curr.pop()

        backtrack(1, k, [], 0)
        return res

Editorial

Approach: Backtracking

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        results = []

        def backtrack(remain, comb, next_start):
            if remain == 0 and len(comb) == k:
                # make a copy of current combination
                # Otherwise the combination would be reverted in other branch of backtracking.
                results.append(list(comb))
                return
            elif remain < 0 or len(comb) == k:
                # exceed the scope, no need to explore further.
                return

            # Iterate through the reduced list of candidates.
            for i in range(next_start, 9):
                comb.append(i + 1)
                backtrack(remain - i - 1, comb, i + 1)
                # backtrack the current choice
                comb.pop()

        backtrack(n, [], 0)

        return results