Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Combination Sum III

MEDIUMProblemSolveExternal Links

Description

Find all valid combinations of exactly k distinct numbers that sum up to a target value n, subject to the following rules:

  • Only the digits 1 through 9 may be used.
  • Each digit may appear at most once in a single combination.

Return a list of all such valid combinations. The result must not contain duplicate combinations, and the combinations may be returned in any order.

Examples

Example 1

Input: k = 3, n = 7

Output: [[1, 2, 4]]

Explanation: We need exactly 3 different digits from 1-9 that sum to 7. The only valid combination is 1 + 2 + 4 = 7. Other triplets like {1, 2, 3} sum to 6 (too small) and {1, 2, 5} sum to 8 (too large).

Example 2

Input: k = 3, n = 9

Output: [[1, 2, 6], [1, 3, 5], [2, 3, 4]]

Explanation: Three distinct combinations of 3 digits sum to 9:

  • 1 + 2 + 6 = 9
  • 1 + 3 + 5 = 9
  • 2 + 3 + 4 = 9

Note that {1, 4, 4} is not valid because 4 would be used twice, and {3, 3, 3} is invalid for the same reason.

Example 3

Input: k = 4, n = 1

Output: []

Explanation: We need 4 distinct digits from 1-9, but the smallest possible sum using 4 distinct digits is 1 + 2 + 3 + 4 = 10. Since 10 > 1, no valid combination exists and we return an empty list.

Constraints

  • 2 ≤ k ≤ 9
  • 1 ≤ n ≤ 60

Editorial

Brute Force

Intuition

Since we can only use digits 1 through 9, the universe of choices is tiny — just 9 elements. Every possible subset of {1, 2, ..., 9} can be represented by a 9-bit binary number (a bitmask). There are only 2⁹ = 512 such subsets.

The simplest approach is to enumerate every one of these 512 subsets. For each subset, we check two conditions:

  1. Does the subset contain exactly k elements?
  2. Do the elements sum to n?

If both conditions hold, we add that subset to our answer.

Think of it like a checklist of 9 items numbered 1 through 9. You try every possible way of checking off items on the list (512 ways), and for each way you count how many items are checked and add up their numbers. If the count matches k and the total matches n, you record that selection.

Step-by-Step Explanation

Let's trace through with k = 2, n = 5 (we need 2 digits from 1-9 that sum to 5):

We iterate through all 512 bitmasks (0 to 511). Let's focus on the interesting ones:

Step 1: Initialize result as empty. We'll check all masks from 0 to 511.

Step 2: mask = 3 (binary: 000000011) → digits {1, 2}.

  • Count = 2 (matches k=2). Sum = 1 + 2 = 3.
  • 3 ≠ 5. Not valid. Skip.

Step 3: mask = 5 (binary: 000000101) → digits {1, 3}.

  • Count = 2. Sum = 1 + 3 = 4.
  • 4 ≠ 5. Not valid. Skip.

Step 4: mask = 9 (binary: 000001001) → digits {1, 4}.

  • Count = 2. Sum = 1 + 4 = 5.
  • 5 == 5 and count == k! Valid combination [1, 4] found.

Step 5: mask = 6 (binary: 000000110) → digits {2, 3}.

  • Count = 2. Sum = 2 + 3 = 5.
  • 5 == 5 and count == k! Valid combination [2, 3] found.

Step 6: mask = 10 (binary: 000001010) → digits {2, 4}.

  • Count = 2. Sum = 2 + 4 = 6.
  • 6 ≠ 5. Not valid. Skip.

Step 7: We continue checking all remaining masks. No more valid combinations found.

Step 8: Result = [[1, 4], [2, 3]].

Bitmask Enumeration — Checking All 2⁹ Subsets — Watch how we use bitmasks to enumerate subsets of {1..9}, checking each for the correct size k and sum n.

Algorithm

  1. Initialize an empty result list.
  2. Iterate through all bitmasks from 0 to 2⁹ - 1 (i.e., 0 to 511).
  3. For each bitmask:
    a. Count the number of set bits (this is the subset size).
    b. If the count does not equal k, skip this mask.
    c. Compute the sum of all digits whose corresponding bit is set.
    d. If the sum equals n, extract the digits and add the combination to the result.
  4. Return the result list.

Code

class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> result;
        
        // Enumerate all subsets of {1, 2, ..., 9}
        for (int mask = 0; mask < (1 << 9); mask++) {
            int count = 0, sum = 0;
            vector<int> combo;
            
            for (int j = 0; j < 9; j++) {
                if (mask & (1 << j)) {
                    count++;
                    sum += (j + 1);  // digits are 1-indexed
                    combo.push_back(j + 1);
                }
            }
            
            if (count == k && sum == n) {
                result.push_back(combo);
            }
        }
        
        return result;
    }
};
class Solution:
    def combinationSum3(self, k: int, n: int) -> list[list[int]]:
        result = []
        
        # Enumerate all subsets of {1, 2, ..., 9}
        for mask in range(1 << 9):
            combo = []
            total = 0
            
            for j in range(9):
                if mask & (1 << j):
                    combo.append(j + 1)
                    total += (j + 1)
            
            if len(combo) == k and total == n:
                result.append(combo)
        
        return result
class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> result = new ArrayList<>();
        
        // Enumerate all subsets of {1, 2, ..., 9}
        for (int mask = 0; mask < (1 << 9); mask++) {
            int count = 0, sum = 0;
            List<Integer> combo = new ArrayList<>();
            
            for (int j = 0; j < 9; j++) {
                if ((mask & (1 << j)) != 0) {
                    count++;
                    sum += (j + 1);
                    combo.add(j + 1);
                }
            }
            
            if (count == k && sum == n) {
                result.add(combo);
            }
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(2⁹ × 9) = O(4608) ≈ O(1)

We check all 512 bitmasks, and for each mask we scan 9 bit positions. Since both the number of masks and the digit count are fixed constants (independent of the input), this is technically O(1). However, conceptually it is O(2⁹ × 9) — every subset is generated and checked regardless of k and n.

Space Complexity: O(1) (excluding the output)

We use a constant amount of auxiliary space for the current mask, sum, count, and temporary combination. The output size depends on the number of valid combinations, which is at most C(9, k).

Why This Approach Is Not Efficient

While the bitmask brute force works fine for this problem's small fixed input size (digits 1-9), it has a fundamental inefficiency: it examines every possible subset regardless of whether it could possibly be valid.

Consider k = 2, n = 3. The only valid combination is [1, 2]. But the brute force still checks all 512 subsets, including absurd ones like {7, 8, 9} (sum = 24, way too large) and single-element sets (wrong count). Out of 512 masks, it processes all of them even though most can be dismissed immediately.

The key insight is that we can prune entire branches of the search space early:

  • If we've already picked k numbers, stop — we don't need more.
  • If the current number exceeds the remaining sum needed, stop — no point going further.
  • If we process numbers in increasing order, we naturally avoid duplicates.

A backtracking approach exploits these observations. Instead of blindly generating all 512 subsets and filtering, it builds combinations incrementally, abandoning a path the moment it becomes impossible. This results in far fewer operations for most inputs.

Optimal Approach - Backtracking with Pruning

Intuition

Instead of generating all subsets and filtering, we build valid combinations one digit at a time, using a recursive decision process.

Imagine standing in a hallway with 9 doors, labeled 1 through 9. You need to open exactly k doors such that the numbers on those doors add up to n. You start at door 1 and face a choice: open it (include digit 1) or walk past it (exclude digit 1). Then you move to door 2 and repeat.

The clever part is that you carry a mental checklist:

  • How many more doors do I need to open? If you've already opened k doors, stop — you have enough.
  • How much sum do I still need? If the next door's number is bigger than the remaining sum, there's no point opening it or any subsequent door (since door numbers only increase).

This is the essence of backtracking with pruning:

  • Backtracking: Try a choice, explore its consequences, then undo the choice and try the alternative.
  • Pruning: Cut off branches of the search tree early when you can prove they won't lead to a valid answer.

By always considering digits in increasing order (1, then 2, then 3, ...), we automatically avoid generating duplicate combinations.

Step-by-Step Explanation

Let's trace through with k = 3, n = 9:

Step 1: Start at digit 1, remaining sum = 9, current combination = [], need 3 more digits.

Step 2: Include digit 1. Combination = [1], remaining = 9 - 1 = 8, need 2 more.

Step 3: Include digit 2. Combination = [1, 2], remaining = 8 - 2 = 6, need 1 more.

Step 4: Include digit 3. Combination = [1, 2, 3], remaining = 6 - 3 = 3. Need 0 more but remaining ≠ 0. Not valid. Backtrack.

Step 5: Exclude digit 3, try digit 4. Combination = [1, 2, 4], remaining = 6 - 4 = 2. Need 0 more but remaining ≠ 0. Not valid. Backtrack.

Step 6: Exclude digit 4, try digit 5. Combination = [1, 2, 5], remaining = 6 - 5 = 1. Need 0 more but remaining ≠ 0. Not valid. Backtrack.

Step 7: Exclude digit 5, try digit 6. Combination = [1, 2, 6], remaining = 6 - 6 = 0. Need 0 more AND remaining = 0. Valid! Record [1, 2, 6].

Step 8: Backtrack past digit 6. Exclude digit 7 (7 > remaining 6 when we were at [1,2]), so no more options for the [1,2,...] branch. Backtrack to [1].

Step 9: Exclude digit 2, try digit 3. Combination = [1, 3], remaining = 8 - 3 = 5, need 1 more.

Step 10: Include digit 4. Combination = [1, 3, 4], remaining = 5 - 4 = 1. Not valid. Backtrack.

Step 11: Try digit 5. Combination = [1, 3, 5], remaining = 5 - 5 = 0. Valid! Record [1, 3, 5].

Step 12: Continue exploring: [1, 4, ...] through [1, 9, ...] yield no new valid combinations (sums exceed 9 or don't reach 9 with exactly 3 digits).

Step 13: Backtrack to root. Exclude digit 1, try starting with digit 2.

Step 14: Combination [2, 3, 4]: sum = 9, count = 3. Valid! Record [2, 3, 4].

Step 15: Remaining branches with starting digit ≥ 3 are pruned (minimum sum of 3 digits starting from 3 is 3+4+5 = 12 > 9).

Step 16: Final result: [[1, 2, 6], [1, 3, 5], [2, 3, 4]].

Backtracking — Building Combinations with Pruning — Watch the recursive backtracking tree explore digit choices, pruning branches early when the remaining sum or count constraints are violated.

Algorithm

  1. Create a helper function backtrack(start, remaining) where:
    • start is the next digit to consider (begins at 1).
    • remaining is the sum still needed.
  2. Base case: If remaining = 0 and the current combination has exactly k elements, record a copy of the combination and return.
  3. Pruning: If start > 9, or start > remaining, or the combination already has k elements, return immediately.
  4. Include choice: Append start to the current combination, then call backtrack(start + 1, remaining - start).
  5. Undo and exclude: Remove start from the combination, then call backtrack(start + 1, remaining) to explore skipping this digit.
  6. Invoke backtrack(1, n) from the main function.
  7. Return the collected results.

Code

class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> result;
        vector<int> combo;
        
        backtrack(1, n, k, combo, result);
        return result;
    }
    
private:
    void backtrack(int start, int remaining, int k,
                   vector<int>& combo, vector<vector<int>>& result) {
        if (remaining == 0 && (int)combo.size() == k) {
            result.push_back(combo);
            return;
        }
        
        if (start > 9 || start > remaining || (int)combo.size() >= k) {
            return;
        }
        
        // Include current digit
        combo.push_back(start);
        backtrack(start + 1, remaining - start, k, combo, result);
        
        // Exclude current digit (backtrack)
        combo.pop_back();
        backtrack(start + 1, remaining, k, combo, result);
    }
};
class Solution:
    def combinationSum3(self, k: int, n: int) -> list[list[int]]:
        result = []
        combo = []
        
        def backtrack(start: int, remaining: int):
            if remaining == 0 and len(combo) == k:
                result.append(combo[:])
                return
            
            if start > 9 or start > remaining or len(combo) >= k:
                return
            
            # Include current digit
            combo.append(start)
            backtrack(start + 1, remaining - start)
            
            # Exclude current digit (backtrack)
            combo.pop()
            backtrack(start + 1, remaining)
        
        backtrack(1, n)
        return result
class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> combo = new ArrayList<>();
        backtrack(1, n, k, combo, result);
        return result;
    }
    
    private void backtrack(int start, int remaining, int k,
                           List<Integer> combo, List<List<Integer>> result) {
        if (remaining == 0 && combo.size() == k) {
            result.add(new ArrayList<>(combo));
            return;
        }
        
        if (start > 9 || start > remaining || combo.size() >= k) {
            return;
        }
        
        // Include current digit
        combo.add(start);
        backtrack(start + 1, remaining - start, k, combo, result);
        
        // Exclude current digit (backtrack)
        combo.remove(combo.size() - 1);
        backtrack(start + 1, remaining, k, combo, result);
    }
}

Complexity Analysis

Time Complexity: O(C(9, k) × k)

In the worst case, the algorithm explores all valid combinations of k digits from {1, ..., 9}. The number of such combinations is C(9, k) = 9! / (k! × (9-k)!). For each valid combination found, we spend O(k) time to copy it into the result list. However, due to aggressive pruning (cutting branches when the digit exceeds the remaining sum, or when we already have k elements), the actual number of nodes visited in the recursion tree is much smaller than 2⁹. For typical inputs, the pruning eliminates the vast majority of branches.

Space Complexity: O(k)

The recursion stack depth is at most 9 (one level per digit), and the current combination combo holds at most k elements. Since k ≤ 9, the auxiliary space is O(k). The output list is not counted as auxiliary space since it is required by the problem.