Find a lesson, question or project

Start typing to search published content and planned structures.

↑ ↓ moveEnter openEsc close

Combination Sum III in Java: Exactly k Distinct Digits

Understand exactly-k digit combinations with a subset baseline, take/skip recursion, safe sum bounds, commented Java and a complete illustrated dry run.

MediumRecursion and backtrackingPattern: recursion, backtracking

Problem statement

Choose exactly k different numbers from 1..9 so their sum is n. Return every valid value combination once. A number cannot be reused, and changing the order of the same chosen numbers does not create another answer.

Both conditions matter: the sum must match and the list must have exactly k elements. For k=3,n=7, [1,6] has the correct sum but is not a valid answer.

The published constraints are 2≤k≤9 and 1≤n≤60. Here n is the target sum, not the number of available values. The candidate universe always has nine numbers.

Constraints & requirements

CONTRACT
LeetCode: 2≤k≤9 and 1≤n≤60. Both count and sum must match. Advance to the next digit in BOTH take and skip branches; preserve saved answers while restoring the shared path.

Examples 3 test cases

  1. Example 1 Case 1

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

    1+2+4=7 with exactly three distinct allowed digits.

  2. Example 2 Case 2

    Input
    k=3; n=9
    Output
    [[1,2,6],[1,3,5],[2,3,4]]

    The three value combinations are unique; rearrangements are not additional answers.

  3. Example 3 Case 3

    Input
    k=4; n=1
    Output
    []

    Even the smallest four distinct digits sum to 10, which already exceeds 1.

Solve on LeetCode ↗

Hints Optional

Hints become more specific one step at a time.
01Hint 1

A sum of n with fewer or more than k digits is not an answer.

02Hint 2

Choose or skip the current digit, retiring it in either branch.

03Hint 3

Before searching, compare the remaining sum with the smallest and largest sums possible using exactly the remaining slots.

How to think before coding

Compare the three Combination Sum contracts before choosing a template:

Problem Candidate source Reuse Required count
Combination Sum Given distinct positive array Allowed Any count
Combination Sum II Given array, possibly duplicate values Each index once Any count
Combination Sum III Fixed values 1..9 Each value once Exactly k

For III, process one allowed digit at a time. We may take it or skip it, but both branches advance to the next digit. That makes the shared path increasing, so [1,2,4] can be produced but its rearrangement [4,1,2] cannot.

Track remaining rather than repeatedly summing the path. Also track how many values are still needed. A promising sum with too few available digits is still impossible.

Brute force: check all subsets

There are only 2^9=512 subsets of 1..9. A baseline checks every subset, counts selected values and calculates its sum, keeping those that match both conditions. This is correct and practical for the fixed domain.

Backtracking is useful here because it teaches how to reject impossible prefixes before building every full subset. It is a pruning improvement, not a claim that a nine-element baseline is unusable or that every combination problem needs a complicated optimization.

Intuition: sum and count constrain the same suffix

Let next be the smallest digit we have not decided yet. Let slots=k−path.size().

Before branching, check:

  • Are at least slots digits left in next..9?
  • Is the remaining sum at least the sum of the smallest slots available digits?
  • Is it at most the sum of the largest slots available digits?

For next=3, slots=2, the smallest possible suffix is 3+4=7. If remaining=6, no descendant can help; do not enter it.

Deriving the sum bounds

The smallest suffix is the arithmetic sequence next,next+1,...,next+slots−1. Its sum is slots × (2×next+slots−1) / 2.

The largest suffix is 9,8,...,10−slots, with sum slots × (19−slots) / 2. Check that enough digits remain before using these bounds. This ensures those largest digits are actually in the available range.

These guards are safe because all candidates are distinct and positive. They would need reconsideration for a different problem with zeros, negatives or reuse.

Why does the size base case return even on failure?

Once the path contains k digits, appending another would violate the count rule. Save only if remaining==0, then return either way. Reaching a target sum alone is not the base case for this question.

Algorithm

  1. Start with an empty path, next=1 and remaining=n.
  2. At size k, save a list copy only when remaining is zero; then return.
  3. Reject exhausted digits, an overshot target, insufficient available digits or impossible sum bounds.
  4. Take next if it fits: append it, recurse using next+1, and remove it on return.
  5. Skip next: recurse using next+1 without changing remaining or the path.

Java solution

This preserves the take/skip structure of the local practice solution. It adds explicit suffix bounds and uses remove(size−1) for Java 17 compatibility.

Java
import java.util.*;

class Solution {
    public static List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> result = new ArrayList<>();
        chooseDigits(k, n, 1, new ArrayList<>(), result); // Start before choosing any of 1..9.
        return result; // Every saved combination contains exactly k distinct digits.
    }

    private static void chooseDigits(int k, int remaining, int next,
            List<Integer> path, List<List<Integer>> result) {
        if (path.size() == k) { // Reaching the requested size is not sufficient by itself.
            if (remaining == 0) result.add(new ArrayList<>(path)); // Save an independent valid answer.
            return; // No branch may use more than k numbers.
        }
        if (next > 9 || remaining < 0) return; // No available digit, or an overshot positive target.
        int slots = k - path.size(); // How many numbers are still required?
        if (10 - next < slots) return; // Too few distinct digits remain in next..9.
        int minimum = slots * (2 * next + slots - 1) / 2; // next + ... + (next+slots-1).
        int maximum = slots * (19 - slots) / 2; // 9 + 8 + ... using exactly slots digits.
        if (remaining < minimum || remaining > maximum) return; // Even the best possible suffix cannot fit.
        if (next <= remaining) { // All available numbers are positive; a larger one cannot help.
            path.add(next); // Take this digit once.
            chooseDigits(k, remaining - next, next + 1, path, result); // Retire it in the child.
            path.remove(path.size() - 1); // Restore this caller's prefix after its take subtree.
        }
        chooseDigits(k, remaining, next + 1, path, result); // Skip it; do not change the remaining sum.
    }

    public static void main(String[] args) {
        System.out.println(combinationSum3(3, 7)); // [[1, 2, 4]]
        System.out.println(combinationSum3(3, 9)); // [[1, 2, 6], [1, 3, 5], [2, 3, 4]]
        System.out.println(combinationSum3(4, 1)); // []
    }
}

The main method prints the single combination for (3,7), the three combinations for (3,9), and an empty result for (4,1).

Illustrated dry run

Use k=3,n=7. The pruned search below is complete: it includes the rejected full path [1,2,3], the successful [1,2,4], every undo and the remaining bound-pruned sibling subtrees.

Numbered illustrated dry run for Combination Sum III; the text transcript explains the states.
Follow the numbered panels in order. Open full-size dry run ↗
Read the text transcript

Follow the Java, step by step

Example: k = 3, n = 7

What to track: Each call owns remaining and next; path/result are shared. Both take and skip retire next. Minimum/maximum bounds use exactly the still-needed slots. This is the complete pruned traversal.

  1. Enter with three slots

    Java operationint slots = k - path.size();
    Statenext=1; remaining=7; path=[]; slots=3; minimum=6; maximum=24

    Seven lies between 1+2+3 and 7+8+9, so the root may contain an answer.

  2. Take 1, then take 2

    Java operationchooseDigits(k, remaining - next, next + 1, path, result);
    Statechild (next=2, remaining=6, path=[1]); then (next=3, remaining=4, path=[1,2])

    Increasing next in both children prevents using 1 or 2 again and avoids order-only duplicates.

  3. Reject the full but wrong-size-sum candidate

    Java operationif (remaining == 0) result.add(new ArrayList<>(path));
    Statetake 3 → next=4; remaining=1; path=[1,2,3]; size=k; no answer saved

    Exactly three values have been selected, but they sum to 6 rather than 7. The size base case returns even on failure.

  4. Undo 3 and skip it

    Java operationpath.remove(path.size() - 1);
    Stateresumed caller: next=3, remaining=4, path=[1,2]; skip child: next=4, remaining=4

    The caller keeps its original remaining sum. Its skip branch changes only next, not remaining or the prefix.

  5. Take 4 and save the valid combination

    Java operationresult.add(new ArrayList<>(path));
    Statenext=5; remaining=0; path=[1,2,4]; size=k; result=[[1,2,4]]

    Both required conditions now hold. A list copy survives when the caller removes 4.

  6. Prune after skipping 4

    Java operationif (remaining < minimum || remaining > maximum) return;
    Statenext=5; remaining=4; path=[1,2]; slots=1; minimum=5

    Every remaining digit is at least 5. One positive digit cannot fill a gap of 4.

  7. Undo 2; skip-2 branch cannot fit

    Java operationchooseDigits(k, remaining, next + 1, path, result);
    Statenext=3; remaining=6; path=[1]; slots=2; minimum=3+4=7

    This entire sibling subtree is impossible. It is skipped by the bound rather than by pretending a valid child was explored.

  8. Undo 1 and finish at the root

    Java operationif (remaining < minimum || remaining > maximum) return;
    Stateroot skip child: next=2; remaining=7; path=[]; slots=3; minimum=2+3+4=9

    The only remaining root subtree cannot reach 7. The saved answer remains, while the shared path ends empty.

Final result: [[1,2,4]]; all caller prefixes are restored after their branches.

When following a return, restore the caller’s path and read the caller’s original remaining value. The child received a smaller integer; it did not overwrite the parent’s local variable.

Why it works

Legal paths: Every taken digit lies in 1..9. Both branches retire that digit, so selected values are distinct and increasing.

Correct saves: A path is saved only when its length is k and its remaining sum is zero. Every saved answer therefore satisfies both requirements.

Complete search: Any valid combination makes exactly one take/skip choice for each digit. The algorithm follows that unique decision path unless a bound proves that no completion exists. Such a proof cannot remove a valid answer.

No duplicates: There is only one increasing take/skip representation of a chosen set. We do not need a HashSet to remove permutations afterward.

Complexity and alternative approaches

For explanation, let m be the size of the candidate universe; in this exact problem, m=9. Let R be the number of answers.

Approach Time Extra space Tradeoff
Enumerate bitmasks and scan each subset O(m × 2^m + kR) O(m), excluding answers Small, exhaustive baseline
Take/skip with suffix bounds O(2^m + kR) upper bound O(m), excluding answers Constant-time checks can discard whole subtrees

Both searches are bounded by a small fixed universe here. Returning R independent length-k lists needs O(kR) space and copy work.

The path holds at most k values, but the recursion can also contain skip calls. Its depth is bounded by m, not just by k. Do not label total auxiliary space O(k) while ignoring those frames.

Common mistakes

  • Saving [1,6] for k=3 just because its sum is 7.
  • Passing next unchanged in the take branch, accidentally allowing reuse.
  • Changing remaining in the skip branch.
  • Saving the shared list without copying it.
  • Returning after the first saved combination; (3,9) has three.
  • Applying the minimum bound before checking that enough digits remain.
  • Describing the exponential factor using target n rather than the nine available digits.

Practice next

Next lessonCombination Sum

Back to Recursion and backtracking →