Log inSign up
mediumLeetCodeNot Started

Combination Sum III

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Backtracking
Solve on LeetCode
Lesson

Problem Statement

Find all valid combinations of k numbers that sum up to n such that the following conditions are true:

* Only numbers from 1 to 9 are used. * Each number is used at most once.

Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.

Example 1 · 3 Numbers Summing to 7:

Input: k = 3, n = 7
Output: [[1, 2, 4]]
Explanation: 1 + 2 + 4 = 7. There are no other valid combinations.

Example 2 · 3 Numbers Summing to 9:

Input: k = 3, n = 9
Output: [[1, 2, 6], [1, 3, 5], [2, 3, 4]]
Explanation: 1+2+6 = 9, 1+3+5 = 9, 2+3+4 = 9.

Example 3 · No Combination Possible:

Input: k = 4, n = 1
Output: []
Explanation: The minimum possible sum of 4 numbers is 1+2+3+4 = 10, which is greater than 1.

Constraints:

  • 2 <= k <= 9
  • 1 <= n <= 60

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master bounded-domain search where domain is strictly digits 1 to 9.
  • Implement combined depth-bounded (k) and sum-bounded (n) pruning.
  • Analyze exact combinatorial bounds C(9, k).

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Fixed number of elements k
  • Digits constrained strictly between 1 and 9
  • No duplicate digits allowed in a combination

Algorithmic Decision Tree:

  • Loop digit from start to 9.
  • If digit > remaining_n, break loop (early pruning).
  • If current.length == k, record solution if remaining_n == 0 and return.

Connected Patterns:

Combination SumCombinationsSubsets

1. Bitmask Exhaustive Enumeration (1 to 2^9 - 1)

Intuition

Each subset of {1..9} can be represented by a 9-bit integer mask from 1 to (1<<9)-1. For each mask, count set bits. If set bits == k, compute sum of corresponding numbers. If sum == n, add subset to result.

When to apply: Feasible because domain size is fixed at 9 digits.

Algorithm

  1. Loop mask from 1 to (1 << 9) - 1:
  2. - If __builtin_popcount(mask) != k, continue.
  3. - Sum values corresponding to set bits.
  4. - If sum == n, collect combination into result.
  5. Return result.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class Solution {
7public:
8 vector<vector<int>> combinationSum3(int k, int n) {
9 vector<vector<int>> result;
10 for (int mask = 1; mask < (1 << 9); mask++) {
11 if (__builtin_popcount(mask) == k) {
12 int sum = 0;
13 vector<int> current;
14 for (int i = 0; i < 9; i++) {
15 if (mask & (1 << i)) {
16 int val = i + 1;
17 sum += val;
18 current.push_back(val);
19 }
20 }
21 if (sum == n) {
22 result.push_back(current);
23 }
24 }
25 }
26 return result;
27 }
28};
29
30int main() {
31 Solution sol;
32 auto res = sol.combinationSum3(3, 7);
33 for (const auto& c : res) {
34 cout << "[ ";
35 for (int v : c) cout << v << " ";
36 cout << "] ";
37 }
38 cout << endl;
39 return 0;
40}

Time & Space Complexity

  • Time complexity: O(2^9 * 9) = O(1) — Evaluates exactly 512 bitmasks with 9 bit tests each.
  • Space complexity: O(1) — Uses constant memory beyond the output list.

2. Binary Pick / Don't Pick Recursion

Intuition

Function solve(digit, target, current): at each digit from 1 to 9, either include digit and call solve(digit + 1, target - digit, current + [digit]), or skip digit and call solve(digit + 1, target, current).

When to apply: Alternative recursive view without for loops.

Algorithm

  1. Base condition: If current.length == k, if target == 0 add to result; return.
  2. If digit > 9 or target < 0, return.
  3. Pick: current.push(digit), solve(digit + 1, target - digit), current.pop().
  4. Don't Pick: solve(digit + 1, target).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class Solution {
7 void solve(int digit, int k, int n, vector<int>& current, vector<vector<int>>& result) {
8 if (current.size() == k) {
9 if (n == 0) result.push_back(current);
10 return;
11 }
12 if (digit > 9 || n < 0) return;
13
14 // Pick digit
15 current.push_back(digit);
16 solve(digit + 1, k, n - digit, current, result);
17 current.pop_back();
18
19 // Don't pick digit
20 solve(digit + 1, k, n, current, result);
21 }
22
23public:
24 vector<vector<int>> combinationSum3(int k, int n) {
25 vector<vector<int>> result;
26 vector<int> current;
27 solve(1, k, n, current, result);
28 return result;
29 }
30};
31
32int main() {
33 Solution sol;
34 auto res = sol.combinationSum3(3, 7);
35 for (const auto& c : res) {
36 cout << "[ ";
37 for (int v : c) cout << v << " ";
38 cout << "] ";
39 }
40 cout << endl;
41 return 0;
42}

Time & Space Complexity

  • Time complexity: O(2^9 * k) = O(1) — Traverses a binary tree of maximum depth 9.
  • Space complexity: O(k) — Recursion depth is bounded by k.

3. Backtracking with Loop & Early Pruning (Optimal)

Intuition

Iterate i from start to 9. If i > remaining_target, break immediately. If current.length + (9 - i + 1) < k, we cannot possibly pick enough digits, so prune. When current.length == k and target == 0, save combination.

When to apply: The definitive optimal solution for Combination Sum III.

Algorithm

  1. Define backtrack(start, k, target, current):
  2. - If current.length == k:
  3. - If target == 0, add copy of current to result.
  4. - Return.
  5. - Loop i from start to 9:
  6. - If i > target, break (early sum pruning).
  7. - If current.length + (9 - i + 1) < k, break (insufficient digits pruning).
  8. - Push i to current.
  9. - Recurse backtrack(i + 1, k, target - i, current).
  10. - Pop i from current.
  11. Return result.

Bounded Combination Search Trace

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
Initial state: k = 3, rem = 7, start = 1, path = []
Visual state
Values and pointers at this exact step
tree
Root
rem: 7, len: 0

Node order shown; add connections to display explicit tree edges.

Variables at this step
k
3
target
7
current
[]
Why this step matters

Initial state: k = 3, rem = 7, start = 1, path = [].

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class Solution {
7 void backtrack(int start, int k, int n, vector<int>& current, vector<vector<int>>& result) {
8 if (current.size() == k) {
9 if (n == 0) result.push_back(current);
10 return;
11 }
12
13 for (int i = start; i <= 9; i++) {
14 if (i > n) break; // Sum pruning
15 if (current.size() + (9 - i + 1) < k) break; // Count pruning
16
17 current.push_back(i);
18 backtrack(i + 1, k, n - i, current, result);
19 current.pop_back(); // backtrack
20 }
21 }
22
23public:
24 vector<vector<int>> combinationSum3(int k, int n) {
25 vector<vector<int>> result;
26 vector<int> current;
27 backtrack(1, k, n, current, result);
28 return result;
29 }
30};
31
32int main() {
33 Solution sol;
34 auto res = sol.combinationSum3(3, 7);
35 for (const auto& c : res) {
36 cout << "[ ";
37 for (int v : c) cout << v << " ";
38 cout << "] ";
39 }
40 cout << endl;
41 return 0;
42}

Time & Space Complexity

  • Time complexity: O(C(9, k) * k) — Generates exactly C(9, k) combination branches, bounded by at most 126 states.
  • Space complexity: O(k) — Recursion depth is strictly bounded by k (at most 9 frames).

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Bitmask Exhaustive EnumerationO(2^9 * 9) = O(1)O(1)Iterate all 512 bitmasks and test popcount == k && sum == n.Static 512 mask iteration
2.Binary Pick / Don't Pick RecursionO(2^9 * k) = O(1)O(k)Binary decisions for each digit 1..9.Binary tree call frames
3.Backtracking with Loop & Early PruningOptimalO(C(9, k) * k)O(k)Loop 1..9 with dual sum and count pruning.Bounded subset exploration

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Allowing digits > 9 or digits == 0 (problem specifies digits 1..9 strictly).

Pitfall 2:

Forgetting to check current.length == k before checking target == 0.

Pitfall 3:

Not copying the current list when pushing to result.

Crucial Edge Cases to Validate:

  • Target Too Small for k Numbers: k = 4, n = 1 -> returns [] (min sum is 1+2+3+4 = 10).
  • Target Too Large for k Numbers: k = 3, n = 30 -> returns [] (max sum is 7+8+9 = 24).
  • Maximum Valid Target: k = 9, n = 45 -> returns [[1, 2, 3, 4, 5, 6, 7, 8, 9]].

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Mention the mathematical maximum bounds C(9, k) <= 126 upfront to impress the interviewer with complexity analysis.
  2. Explain both sum pruning (i > target) and count pruning (current.length + (9 - i + 1) < k).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the maximum number of combinations generated by Combination Sum III for any valid k?

2.What does the pruning condition current.length + (9 - i + 1) < k check?

Back to DSA Sheet