Combination Sum III solution and explanation
Google
9 more videos on this problem
Combination Sum iii | LeetCode 216 | C++, Java, PythonKnowledge Center · 23:00 · 13K views
Combination Sum III | Leetcode 216 | Backtracking | Day-10Ayushi Sharma · 17:09 · 11K views
combination sum iii | Combination Sum III | leetcode 216 | backtrackingNaresh Gupta · 8:51 · 9K views
Combination Sum III | Leetcode | Medium | Java | Recursion | Striver's A to Z DSA SheetAlgorithmHQ · 7:10 · 4K views
Combination Sum III - LeetCode 216 - Python #backtracking #leetcode #combinationsDeepti Talesra · 13:52 · 3K views
LEETCODE 216 (JAVASCRIPT) | COMBINATION SUM IIIAndy Gala · 15:51 · 3K views
Combination Sum III | Leet code 216 | Theory explained + Python codeSai Anish Malla · 13:26 · 3K views
Leetcode 216. Combination Sum IIIFraz · 4:16 · 2K views
Combination Sum III - LeetCode 216 - JavaScriptAlgoJS · 5:44 · 1K views
Ep14- Combination Sum 3 | Medium level Recursion Problem | DSA | Codes available in descriptionLearnYard · 22:04 · 16K views
The problem
Find all valid combinations of k numbers that sum up to n such that the following conditions are true:
- Only numbers
1through9are 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 <= 91 <= 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.
def combinationSum3(k, n):
def backtrack(k, n, start, path, results):
if k == 0 and n == 0:
results.append(list(path))
return
for i in range(start, 10):
if n < i:
break
path.append(i)
backtrack(k - 1, n - i, i + 1, path, results)
path.pop()
results = []
backtrack(k, n, 1, [], results)
return results
# Example Usage:
# print(combinationSum3(3, 7))import java.util.ArrayList;
import java.util.List;
public class CombinationSum3 {
private void backtrack(int k, int n, int start, List<Integer> path, List<List<Integer>> results) {
if (k == 0 && n == 0) {
results.add(new ArrayList<>(path));
return;
}
for (int i = start; i <= 9; i++) {
if (i > n) break;
path.add(i);
backtrack(k - 1, n - i, i + 1, path, results);
path.remove(path.size() - 1);
}
}
public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> results = new ArrayList<>();
backtrack(k, n, 1, new ArrayList<>(), results);
return results;
}
public static void main(String[] args) {
CombinationSum3 solver = new CombinationSum3();
List<List<Integer>> result = solver.combinationSum3(3, 7);
for (List<Integer> list : result) {
System.out.println(list);
}
}
}#include <vector>
using namespace std;
void backtrack(int k, int n, int start, vector<int>& path, vector<vector<int>>& results) {
if (k == 0 && n == 0) {
results.push_back(path);
return;
}
for (int i = start; i <= 9; ++i) {
if (i > n) break;
path.push_back(i);
backtrack(k - 1, n - i, i + 1, path, results);
path.pop_back();
}
}
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> results;
vector<int> path;
backtrack(k, n, 1, path, results);
return results;
}
// Example usage:
// vector<vector<int>> result = combinationSum3(3, 7);
// for (const auto& seq : result) {
// for (int num : seq) {
// cout << num << ' ';
// }
// cout << endl;
// }var combinationSum3 = function(k, n) {
const results = [];
function backtrack(k, n, start, path) {
if (k === 0 && n === 0) {
results.push([...path]);
return;
}
for (let i = start; i <= 9; i++) {
if (n < i) break;
path.push(i);
backtrack(k - 1, n - i, i + 1, path);
path.pop();
}
}
backtrack(k, n, 1, []);
return results;
};
// Example Usage:
// console.log(combinationSum3(3, 7));#include <stdio.h>
#include <stdlib.h>
void backtrack(int k, int n, int start, int* path, int pathSize, int** results, int* returnSize) {
if (k == 0 && n == 0) {
results[*returnSize] = (int*)malloc(sizeof(int) * pathSize);
for(int i = 0; i < pathSize; i++) {
results[*returnSize][i] = path[i];
}
(*returnSize)++;
return;
}
for (int i = start; i <= 9; i++) {
if (i > n) break;
path[pathSize] = i;
backtrack(k - 1, n - i, i + 1, path, pathSize + 1, results, returnSize);
}
}
int** combinationSum3(int k, int n, int* returnSize, int** returnColumnSizes) {
int path[9];
int** results = malloc(100 * sizeof(int*));
*returnSize = 0;
backtrack(k, n, 1, path, 0, results, returnSize);
*returnColumnSizes = malloc(sizeof(int) * (*returnSize));
for (int i = 0; i < (*returnSize); i++) {
(*returnColumnSizes)[i] = k;
}
return results;
}
int main() {
int size;
int* columnSizes;
int** results = combinationSum3(3, 7, &size, &columnSizes);
for (int i = 0; i < size; i++) {
printf("[");
for (int j = 0; j < columnSizes[i]; j++) {
printf("%d", results[i][j]);
if (j < columnSizes[i] - 1) printf(", ");
}
printf("]\n");
free(results[i]);
}
free(results);
free(columnSizes);
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public IList<IList<int>> CombinationSum3(int k, int n) {
IList<IList<int>> results = new List<IList<int>>();
Backtrack(k, n, 1, new List<int>(), results);
return results;
}
private void Backtrack(int k, int n, int start, List<int> path, IList<IList<int>> results) {
if (k == 0 && n == 0) {
results.Add(new List<int>(path));
return;
}
for (int i = start; i <= 9; i++) {
if (i > n) break;
path.Add(i);
Backtrack(k - 1, n - i, i + 1, path, results);
path.RemoveAt(path.Count - 1);
}
}
public static void Main() {
Solution sol = new Solution();
IList<IList<int>> result = sol.CombinationSum3(3, 7);
foreach (var list in result) {
Console.WriteLine(string.Join(", ", list));
}
}
}This Python example similarly utilizes a recursive backtracking approach. The helper function backtrack attempts all combinations from start to 9 using recursion. Solutions are added to results when valid combinations are identified.
Time Complexity: O(2^n) due to combination paths.
Space Complexity: O(k), related to depth of recursion.
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.
def combinationSum3(k, n):
result = []
for mask in range(1 << 9):
comb = []
total = 0
for i in range(9):
if (mask & (1 << i)) != 0:
total += (i + 1)
comb.append(i + 1)
if len(comb) == k and total == n:
result.append(comb)
return result
# Example Usage:
# print(combinationSum3(3, 7))import java.util.ArrayList;
import java.util.List;
public class CombinationSum3Iterative {
public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> result = new ArrayList<>();
for (int mask = 0; mask < (1 << 9); ++mask) {
List<Integer> comb = new ArrayList<>();
int sum = 0;
for (int i = 0; i < 9; ++i) {
if ((mask & (1 << i)) != 0) {
sum += (i + 1);
comb.add(i + 1);
}
}
if (comb.size() == k && sum == n) {
result.add(new ArrayList<>(comb));
}
}
return result;
}
public static void main(String[] args) {
CombinationSum3Iterative solver = new CombinationSum3Iterative();
List<List<Integer>> result = solver.combinationSum3(3, 7);
for (List<Integer> list : result) {
System.out.println(list);
}
}
}#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> result;
for (int mask = 0; mask < (1 << 9); ++mask) {
vector<int> comb;
int sum = 0;
for (int i = 0; i < 9; ++i) {
if (mask & (1 << i)) {
sum += (i + 1);
comb.push_back(i + 1);
}
}
if (comb.size() == k && sum == n) {
result.push_back(comb);
}
}
return result;
}
// Example usage:
// int main() {
// vector<vector<int>> result = combinationSum3(3, 7);
// for (const auto& comb : result) {
// for (int num : comb) {
// cout << num << ' ';
// }
// cout << endl;
// }
// return 0;
// }var combinationSum3 = function(k, n) {
const results = [];
for (let mask = 0; mask < (1 << 9); ++mask) {
const comb = [];
let sum = 0;
for (let i = 0; i < 9; ++i) {
if ((mask & (1 << i)) !== 0) {
sum += (i + 1);
comb.push(i + 1);
}
}
if (comb.length === k && sum === n) {
results.push(comb);
}
}
return results;
};
// Example Usage:
// console.log(combinationSum3(3, 7));#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
bool *used = NULL;
void printCombination(int *comb, int size) {
printf("[");
for (int i = 0; i < size; i++) {
printf("%d", comb[i]);
if (i != size - 1) printf(", ");
}
printf("]\n");
}
void combine(int n, int k, int *start, int *data, int index) {
if (index == k) {
int sum = 0;
for (int i = 0; i < k; i++) {
sum += data[i];
}
if (sum == n) {
printCombination(data, k);
}
return;
}
for (int i = *start; i <= 9 && k-index <= 9-i+1; i++) {
data[index] = i;
combine(n, k, &(i + 1), data, index + 1);
while (i < 9 && used[i + 1]) i++;
}
}
int main() {
int k = 3, n = 7;
int data[k];
int start = 1;
used = (bool *)malloc(10 * sizeof(bool));
combine(n, k, &start, data, 0);
free(used);
return 0;
}using System;
using System.Collections.Generic;
public class CombinationSum3Iterative {
public IList<IList<int>> CombinationSum3(int k, int n) {
IList<IList<int>> result = new List<IList<int>>();
for (int mask = 0; mask < (1 << 9); ++mask) {
List<int> comb = new List<int>();
int sum = 0;
for (int i = 0; i < 9; ++i) {
if ((mask & (1 << i)) != 0) {
sum += (i + 1);
comb.Add(i + 1);
}
}
if (comb.Count == k && sum == n) {
result.Add(new List<int>(comb));
}
}
return result;
}
public static void Main() {
CombinationSum3Iterative solution = new CombinationSum3Iterative();
var result = solution.CombinationSum3(3, 7);
foreach (var set in result) {
Console.WriteLine(string.Join(", ", set));
}
}
}In Python, bitmasking iterates across all 512 combinations of using numbers 1 through 9. Post-filtering by sum and size k, successful combinations residing in result meet the objectives.
Time Complexity: O(2^9) for subset enumeration of 9 items.
Space Complexity: O(k) owing to subset storage capacity requirements.
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 = 0and the length of the current search pathtisk, it means that a group of answers has been found. Addttoansand then return. - If
i \gt 9ori \gt sor the length of the current search pathtis greater thank, it means that the current search path cannot be the answer, so return directly. - Otherwise, we can choose to add the number
ito the search patht, and then continue to search, i.e., executedfs(i + 1, s - i). After the search is completed, removeifrom the search patht; we can also choose not to add the numberito the search patht, and directly executedfs(i + 1, s).
function combinationSum3(k: number, n: number): number[][] {
const ans: number[][] = [];
const t: number[] = [];
const dfs = (i: number, s: number) => {
if (s === 0) {
if (t.length === k) {
ans.push(t.slice());
}
return;
}
if (i > 9 || i > s || t.length >= k) {
return;
}
t.push(i);
dfs(i + 1, s - i);
t.pop();
dfs(i + 1, s);
};
dfs(1, n);
return ans;
}func combinationSum3(k int, n int) (ans [][]int) {
t := []int{}
var dfs func(i, s int)
dfs = func(i, s int) {
if s == 0 {
if len(t) == k {
ans = append(ans, slices.Clone(t))
}
return
}
if i > 9 || i > s || len(t) >= k {
return
}
t = append(t, i)
dfs(i+1, s-i)
t = t[:len(t)-1]
dfs(i+1, s)
}
dfs(1, n)
return
}impl Solution {
#[allow(dead_code)]
pub fn combination_sum3(k: i32, n: i32) -> Vec<Vec<i32>> {
let mut ret = Vec::new();
let mut candidates = (1..=9).collect();
let mut cur_vec = Vec::new();
Self::dfs(n, k, 0, 0, &mut cur_vec, &mut candidates, &mut ret);
ret
}
#[allow(dead_code)]
fn dfs(
target: i32,
length: i32,
cur_index: usize,
cur_sum: i32,
cur_vec: &mut Vec<i32>,
candidates: &Vec<i32>,
ans: &mut Vec<Vec<i32>>,
) {
if cur_sum > target || cur_vec.len() > (length as usize) {
// No answer for this
return;
}
if cur_sum == target && cur_vec.len() == (length as usize) {
// We get an answer
ans.push(cur_vec.clone());
return;
}
for i in cur_index..candidates.len() {
cur_vec.push(candidates[i]);
Self::dfs(
target,
length,
i + 1,
cur_sum + candidates[i],
cur_vec,
candidates,
ans,
);
cur_vec.pop().unwrap();
}
}
}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:
function combinationSum3(k: number, n: number): number[][] {
const ans: number[][] = [];
for (let mask = 0; mask < 1 << 9; ++mask) {
if (bitCount(mask) === k) {
const t: number[] = [];
let s = 0;
for (let i = 0; i < 9; ++i) {
if (mask & (1 << i)) {
t.push(i + 1);
s += i + 1;
}
}
if (s === n) {
ans.push(t);
}
}
}
return ans;
}
function bitCount(i: number): number {
i = i - ((i >>> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
i = (i + (i >>> 4)) & 0x0f0f0f0f;
i = i + (i >>> 8);
i = i + (i >>> 16);
return i & 0x3f;
}func combinationSum3(k int, n int) (ans [][]int) {
for mask := 0; mask < 1<<9; mask++ {
if bits.OnesCount(uint(mask)) == k {
t := []int{}
s := 0
for i := 0; i < 9; i++ {
if mask>>i&1 == 1 {
s += i + 1
t = append(t, i+1)
}
}
if s == n {
ans = append(ans, t)
}
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Backtracking approach | Time Complexity: Space Complexity: |
| Iterative with bitmasking | Time Complexity: Space Complexity: |
| Pruning + Backtracking (Two Approaches) | – |
| Binary Enumeration | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking | O(2^9) | O(k) | Best general solution for generating valid combinations with pruning |
| Iterative Bitmasking | O(2^9 * 9) | O(1) | When enumerating all subsets or demonstrating bitmask subset techniques |
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.