{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Combination Sum III – Solution & Complexity

Interview solutions
/
Combination Sum III

Solution Walkthrough

  1. Step 1: Recognize the search space

    • You are choosing exactly k distinct digits from the fixed set 1..9, so this is a small combinatorial backtracking problem.
    • Distinctness and increasing order come naturally if each recursive call only considers later digits than the one just chosen.
    • Because each level tries digits in ascending order, the DFS itself produces the required canonical output order without any post-sorting.

  2. Step 2: Plain backtracking with increasing digits

    • Keep a path for the current combination, a start digit for the next choice, and the running sum so far.
    • If the path already has k digits, record it only when the sum is exactly n.
    • Otherwise, try every next digit from start through 9, recurse with digit + 1, then undo the choice.
    • This baseline already guarantees no repeated digits, increasing order inside each combination, and canonical DFS order across the answer list.
    def combination_sum3(k: int, n: int) -> list[list[int]]:
    answer: list[list[int]] = []
    path: list[int] = []

    def backtrack(start: int, total: int) -> None:
        if len(path) == k:
            if total == n:
                answer.append(path.copy())
            return
        if total > n:
            return

        for digit in range(start, 10):
            path.append(digit)
            backtrack(digit + 1, total + digit)
            path.pop()

    backtrack(1, 0)
    return answer

  3. Step 3: Prune impossible branches earlier

    • The baseline works because the search space is tiny, but you can cut many branches before recursing.
    • If you still need remaining_count digits, the smallest possible extra sum comes from taking the next remaining_count consecutive digits starting at start.
    • The largest possible extra sum comes from taking the biggest remaining_count digits ending at 9.
    • If remaining_sum falls outside that [min_possible, max_possible] range, this branch can never succeed and should stop immediately.

  4. Step 4: Final optimized solution and complexity

    Backtracking still explores combinations in the exact same canonical order, but arithmetic bounds prune branches whose remaining slots cannot possibly add up to the target. The search uses O(k) extra recursion/path space, and the total work is O(C(9, k) * k) in the worst case because every valid or explored combination prefix has length at most k.

    def combination_sum3(k: int, n: int) -> list[list[int]]:
    answer: list[list[int]] = []
    path: list[int] = []

    def backtrack(start: int, remaining_count: int, remaining_sum: int) -> None:
        if remaining_count == 0:
            if remaining_sum == 0:
                answer.append(path.copy())
            return

        if 10 - start < remaining_count:
            return

        min_possible = remaining_count * (2 * start + remaining_count - 1) // 2
        max_start = 10 - remaining_count
        max_possible = remaining_count * (max_start + 9) // 2
        if remaining_sum < min_possible or remaining_sum > max_possible:
            return

        for digit in range(start, 10):
            if digit > remaining_sum:
                break
            path.append(digit)
            backtrack(digit + 1, remaining_count - 1, remaining_sum - digit)
            path.pop()

    backtrack(1, k, n)
    return answer

FAQ

See also

Practice Combination Sum III online (run code in the browser)Generate Parentheses solution (medium)Combination Sum solution (medium)Combination Sum II solution (medium)Design Add and Search Words solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?