Skip to main content
Talentd

Combination Sum III - Solution & Explanation

MediumArrayBacktracking31 min readAsked at: Amazon, Microsoft, Google +1
Practice this problem

Problem Statement

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

  • Only numbers 1 through 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:

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

Example 2:

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
There are no other valid combinations.

Example 3:

Input: k = 4, n = 1
Output: []
Explanation: There are no valid combinations.
Using 4 different numbers in the range [1,9], the smallest sum we can get is 1+2+3+4 = 10 and since 10 > 1, there are no valid combination.

 

Constraints:

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

Approach Overview

Problem Overview: You must pick exactly k distinct numbers from 1..9 so their sum equals n. Each number can be used once, and the result should include all valid combinations without duplicates.

Approach 1: Backtracking (O(2^9) time, O(k) space)

This problem naturally fits backtracking. Start from number 1 and recursively build combinations by choosing the next number and reducing the remaining sum. Stop exploring a path when the combination size exceeds k or the sum becomes negative. When the combination length equals k and the remaining sum is 0, record the result. Since the search space only includes numbers 1..9, the recursion tree is small, making the effective time complexity about O(2^9) and space O(k) for the recursion stack and current path.

Approach 2: Iterative with Bitmasking (O(2^9 * 9) time, O(1) space)

You can enumerate every subset of numbers 1..9 using a bitmask from 0 to (1<<9) - 1. Each bit represents whether a number is included in the subset. For each mask, iterate through the bits, count how many numbers are chosen, and compute their sum. If the subset size equals k and the sum equals n, add it to the result. This approach treats the problem like a subset enumeration on an array of numbers and uses a classic bitmasking pattern. Time complexity is O(2^9 * 9) because every mask checks up to nine bits, while space complexity is O(1) excluding the output.

Recommended for interviews: Backtracking is the expected approach. Interviewers want to see how you prune invalid states early (sum exceeded, size exceeded) and generate combinations without duplicates. The bitmasking method demonstrates good understanding of subset enumeration, but backtracking better shows your ability to control the search space and write clean recursive logic.

Approach 1: Backtracking approach

This approach uses backtracking to explore all possible combinations. Start with an empty combination, then add numbers incrementally and explore subsequent possibilities. If the sum of combination exceeds n or if it reaches the required length k, backtracking occurs to explore other potential combinations.

This C code leverages recursion to implement a backtracking solution. It uses the backtrack function recursively to explore combinations of numbers from 1 to 9, which decreases the target sum and the number of numbers to pick. When a valid combination is found (sum equals n and length k), it adds it to the results. Memory management is handled carefully for arrays.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(2^n) because each number has a choice of being included or not.

Space Complexity: O(k) for the recursion stack.

Try this approach in the editor →

Approach 2: Iterative with bitmasking

This approach leverages bitmasking to generate all subsets of numbers {1,2,...,9} and filters conceivable combinations by size and sum criteria. It's potentially less intuitive, yet eliminates recursion.

Utilizing bitmasking in C via manual iteration replacement, the core function combine employs increment logic to attempt each mask permutation across numbers [1,2,…,9]. Valid combinations are printed, as demonstrated. Particular attention is paid to inclusive continuity of sequence generation.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(2^n), iterating through bitmask combinations for validity checks.

Space Complexity: O(k) due to maintained size of data array.

Try this approach in the editor →

Approach 3: Pruning + Backtracking (Two Approaches)

We design a function dfs(i, s), which represents that we are currently enumerating the number i, and there are still numbers with a sum of s to be enumerated. The current search path is t, and the answer is ans.

The execution logic of the function dfs(i, s) is as follows:

Approach One:

  • If s = 0 and the length of the current search path t is k, it means that a group of answers has been found. Add t to ans and then return.
  • If i \gt 9 or i \gt s or the length of the current search path t is greater than k, it means that the current search path cannot be the answer, so return directly.
  • Otherwise, we can choose to add the number i to the search path t, and then continue to search, i.e., execute dfs(i + 1, s - i). After the search is completed, remove i from the search path t; we can also choose not to add the number i to the search path t, and directly execute dfs(i + 1, s).

Code

PythonJavaC++GoTypeScriptJavaScriptRustC#

Python

Java

C++

Go

TypeScript

JavaScript

Rust

C#

Try this approach in the editor →

Approach 4: Binary Enumeration

We can use a binary integer of length 9 to represent the selection of numbers 1 to 9, where the i-th bit of the binary integer represents whether the number i + 1 is selected. If the i-th bit is 1, it means that the number i + 1 is selected, otherwise, it means that the number i + 1 is not selected.

We enumerate binary integers in the range of [0, 2^9). For the currently enumerated binary integer mask, if the number of 1s in the binary representation of mask is k, and the sum of the numbers corresponding to 1 in the binary representation of mask is n, it means that the number selection scheme corresponding to mask is a group of answers. We can add the number selection scheme corresponding to mask to the answer.

The time complexity is O(2^9 times 9), and the space complexity is O(k).

Similar problems:

Code

PythonJavaC++GoTypeScriptJavaScriptC#

Python

Java

C++

Go

TypeScript

JavaScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Backtracking approach

Time Complexity: O(2^n) because each number has a choice of being included or not.

Space Complexity: O(k) for the recursion stack.

Iterative with bitmasking

Time Complexity: O(2^n), iterating through bitmask combinations for validity checks.

Space Complexity: O(k) due to maintained size of data array.

Pruning + Backtracking (Two Approaches)—
Binary Enumeration—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
BacktrackingO(2^9)O(k)Best general solution for generating valid combinations with pruning
Iterative BitmaskingO(2^9 * 9)O(1)When enumerating all subsets or demonstrating bitmask subset techniques

Video Solution

Ep14- Combination Sum 3 | Medium level Recursion Problem | DSA | Codes available in description • LearnYard • 16,801 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Combination Sum III easy or hard?
Combination Sum III is generally rated Medium difficulty. The constraints are small, but the problem requires understanding how to generate combinations with recursion and prune invalid paths efficiently.
Combination Sum III Python/Java solution
Python and Java implementations typically use recursive backtracking. Start from a candidate number, append it to the current path, reduce the remaining sum, and recursively continue with the next number. When the path length equals k and the remaining sum is zero, add the combination to the result list.
How to solve Combination Sum III in O(n)?
An O(n) solution is not possible because the problem requires exploring combinations of numbers. The optimal approach is backtracking with pruning, which effectively explores a small subset of the 2^9 possible combinations. This keeps the runtime manageable despite being exponential in theory.
What is the best approach for Combination Sum III?
Backtracking is the best approach because it generates combinations incrementally and prunes invalid states early. By stopping when the sum exceeds the target or the combination size exceeds k, the search space stays small. The effective complexity is about O(2^9) since the numbers are limited to 1 through 9.
Is Combination Sum III asked at Google/Amazon/Meta?
Combination-style backtracking problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variants such as Combination Sum, Subsets, and Combination Sum II are common. This problem specifically tests recursion, pruning, and combinatorial generation.
What data structure is used in Combination Sum III?
The solution mainly uses a dynamic list or array to store the current combination while exploring possibilities. Recursion manages the search tree, and results are stored in a list of lists. The algorithmic technique is backtracking rather than a specialized data structure.
What is the time complexity of Combination Sum III?
The typical backtracking solution runs in about O(2^9) time because each number from 1 to 9 can either be included or skipped. The recursion depth is at most k, so auxiliary space is O(k). A bitmask enumeration approach takes O(2^9 * 9) time because each subset checks up to nine elements.

Ready to solve this problem?

Practice Combination Sum III with our built-in code editor and test cases.

Practice on FleetCode
Previous

Combination Sum