Combination Sum solution and explanation
Google
9 more videos on this problem
L8. Combination Sum | Recursion | Leetcode | C++ | Javatake U forward · 27:00 · 983K views
Combination Sum - Backtracking - Leetcode 39 - PythonNeetCode · 15:10 · 481K views
combination sum | combination sum leetcode | leetcode 39 | backtracking | Amazon Facebook AdobeNaresh Gupta · 9:29 · 39K views
Combination Sum - Leetcode 39 - Recursive Backtracking (Python)Greg Hogg · 10:29 · 26K views
LeetCode 39 | Combination Sum | Algorithm Explained (Java)Xavier Elon · 12:46 · 12K views
Leetcode 39. Combination SumFraz · 9:25 · 7K views
BackTracking Visually Explained | Combination Sum Leetcode 39ByteQuest · 4:33 · 4K views
Combination Sum - LeetCode 39 - Python (Dynamic Programming and Recursive/Backtracking!) #leetcodeDeepti Talesra · 22:25 · 3K views
Combination Sum - LeetCode 39 - JavaScriptAlgoJS · 9:14 · 3K views
LeetCode 39: Combination Sum | C# Solution | Backtracking Approach |Code Scribbler · 10:40 · 1K views
The problem
Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.
The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.
The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.
Example 1:
Input: candidates = [2,3,6,7], target = 7 Output: [[2,2,3],[7]] Explanation: 2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times. 7 is a candidate, and 7 = 7. These are the only two combinations.
Example 2:
Input: candidates = [2,3,5], target = 8 Output: [[2,2,2,2],[2,3,3],[3,5]]
Example 3:
Input: candidates = [2], target = 1 Output: []
Constraints:
1 <= candidates.length <= 302 <= candidates[i] <= 40- All elements of
candidatesare distinct. 1 <= target <= 40
Approach overview
Problem Overview: Given an array of distinct integers candidates and a target value, return all unique combinations where the chosen numbers sum to the target. Each number can be used unlimited times. The challenge is generating combinations without duplicates while exploring all valid sums.
Approach 1: Backtracking (Exponential Time, Optimal for Enumeration)
This approach treats the problem as a recursive search tree. Start from index 0, repeatedly choose a candidate, add it to the current combination, and recursively explore the remaining target. If the running sum equals the target, record the combination. If it exceeds the target, stop exploring that path. Because candidates can be reused, the recursive call continues from the same index instead of moving forward.
The key insight is pruning: once the remaining target becomes negative, the branch cannot produce a valid combination. Backtracking efficiently explores possibilities while avoiding unnecessary permutations. Time complexity is exponential, typically O(2^T) in the worst case depending on the target and smallest candidate. Space complexity is O(T) for recursion depth and combination storage. This technique is a classic application of backtracking with recursive exploration over an array.
Approach 2: Dynamic Programming (O(n * target * k))
A dynamic programming strategy builds solutions for every intermediate sum from 0 to target. Use a DP array where dp[i] stores all combinations that produce sum i. Initialize dp[0] with an empty combination. For each candidate number, iterate through target values and extend previously built combinations by appending the candidate.
The advantage of this approach is structured bottom‑up construction. Instead of exploring recursive paths, it reuses previously computed results. Time complexity is roughly O(n * target * k), where n is the number of candidates and k represents the average number of stored combinations. Space complexity is also O(target * k) due to storing all partial combinations. This technique demonstrates a combinational form of dynamic programming.
Recommended for interviews: The backtracking solution is what most interviewers expect. It shows you understand recursive exploration, pruning, and combination generation. Mentioning the dynamic programming variation demonstrates deeper problem-solving breadth, but implementing clean backtracking with correct pruning and duplicate control is usually sufficient for coding interviews.
Approach 1: Backtracking Approach
This approach uses recursion and backtracking to generate all possible combinations by exploring each candidate. If a candidate is chosen, we explore further with the remaining target reduced by the candidate's value. We use backtracking to remove a candidate and try the next one. This way, we explore all possible combinations using depth-first search.
def combinationSum(candidates, target):
def backtrack(remaining, path, start):
if remaining < 0:
return
if remaining == 0:
result.append(list(path))
return
for i in range(start, len(candidates)):
path.append(candidates[i])
backtrack(remaining - candidates[i], path, i)
path.pop()
result = []
backtrack(target, [], 0)
return result
candidates = [2, 3, 6, 7]
target = 7
print(combinationSum(candidates, target))import java.util.ArrayList;
import java.util.List;
public class CombinationSum {
public static void backtrack(int[] candidates, int target, List<List<Integer>> result, List<Integer> tempList, int start) {
if (target < 0) return;
if (target == 0) result.add(new ArrayList<>(tempList));
for (int i = start; i < candidates.length; i++) {
tempList.add(candidates[i]);
backtrack(candidates, target - candidates[i], result, tempList, i);
tempList.remove(tempList.size() - 1);
}
}
public static List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
backtrack(candidates, target, result, new ArrayList<>(), 0);
return result;
}
public static void main(String[] args) {
int[] candidates = {2, 3, 6, 7};
int target = 7;
List<List<Integer>> result = combinationSum(candidates, target);
System.out.println(result);
}
}#include <iostream>
#include <vector>
using namespace std;
void backtrack(vector<int>& candidates, int target, vector<vector<int>>& result, vector<int>& combination, int start) {
if (target < 0) return;
if (target == 0) {
result.push_back(combination);
return;
}
for (int i = start; i < candidates.size(); ++i) {
combination.push_back(candidates[i]);
backtrack(candidates, target - candidates[i], result, combination, i);
combination.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> result;
vector<int> combination;
backtrack(candidates, target, result, combination, 0);
return result;
}
int main() {
vector<int> candidates = {2, 3, 6, 7};
int target = 7;
vector<vector<int>> result = combinationSum(candidates, target);
for (const auto& comb : result) {
cout << "[";
for (int i = 0; i < comb.size(); ++i) {
cout << comb[i] << (i == comb.size() - 1 ? "" : ", ");
}
cout << "]\n";
}
return 0;
}const combinationSum = function(candidates, target) {
const result = [];
function backtrack(remaining, path, start) {
if (remaining < 0) return;
if (remaining === 0) result.push([...path]);
for (let i = start; i < candidates.length; i++) {
path.push(candidates[i]);
backtrack(remaining - candidates[i], path, i);
path.pop();
}
}
backtrack(target, [], 0);
return result;
};
const candidates = [2, 3, 6, 7];
const target = 7;
console.log(combinationSum(candidates, target));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void findCombination(int* candidates, int candidatesSize, int target, int** result, int* returnColSize, int* returnSize, int* currentCombo, int currentComboSize, int startIndex) {
if (target < 0) return;
if (target == 0) {
result[*returnSize] = (int*)malloc(sizeof(int) * currentComboSize);
memcpy(result[*returnSize], currentCombo, sizeof(int) * currentComboSize);
returnColSize[*returnSize] = currentComboSize;
(*returnSize)++;
return;
}
for (int i = startIndex; i < candidatesSize; i++) {
currentCombo[currentComboSize] = candidates[i];
findCombination(candidates, candidatesSize, target - candidates[i], result, returnColSize, returnSize, currentCombo, currentComboSize + 1, i);
}
}
int** combinationSum(int* candidates, int candidatesSize, int target, int** columnSizes, int* returnSize) {
int** result = (int**)malloc(150 * sizeof(int*));
*columnSizes = (int*)malloc(150 * sizeof(int));
*returnSize = 0;
int* currentCombo = (int*)malloc(target * sizeof(int));
findCombination(candidates, candidatesSize, target, result, *columnSizes, returnSize, currentCombo, 0, 0);
free(currentCombo);
return result;
}
int main() {
int candidates[] = {2, 3, 6, 7};
int candidatesSize = 4;
int target = 7;
int* columnSizes;
int returnSize;
int** result = combinationSum(candidates, candidatesSize, target, &columnSizes, &returnSize);
for (int i = 0; i < returnSize; i++) {
printf("[");
for (int j = 0; j < columnSizes[i]; j++) {
printf("%d%s", result[i][j], j == columnSizes[i] - 1 ? "" : ", ");
}
printf("]\n");
free(result[i]);
}
free(result);
free(columnSizes);
return 0;
}using System;
using System.Collections.Generic;
class CombinationSumSolution {
public IList<IList<int>> CombinationSum(int[] candidates, int target) {
IList<IList<int>> result = new List<IList<int>>();
List<int> tempList = new List<int>();
Backtrack(candidates, target, result, tempList, 0);
return result;
}
private void Backtrack(int[] candidates, int target, IList<IList<int>> result, List<int> tempList, int start) {
if (target < 0) return;
if (target == 0) result.Add(new List<int>(tempList));
for (int i = start; i < candidates.Length; i++) {
tempList.Add(candidates[i]);
Backtrack(candidates, target - candidates[i], result, tempList, i);
tempList.RemoveAt(tempList.Count - 1);
}
}
static void Main(string[] args) {
int[] candidates = {2, 3, 6, 7};
int target = 7;
CombinationSumSolution solution = new CombinationSumSolution();
var result = solution.CombinationSum(candidates, target);
foreach (var combination in result) {
Console.WriteLine("[" + string.Join(", ", combination) + "]");
}
}
}This Python implementation defines a recursive backtrack function to explore and solve the problem by selecting candidates starting from the current index for potential reuse, stopping when the target is met or surpassed.
Time Complexity: O(2^T), since multiple paths can be explored.
Space Complexity: O(T), due to recursion and path list storage.
Approach 2: Dynamic Programming Approach
We can use a dynamic programming (DP) approach to solve the Combination Sum problem. We maintain a DP array where each index represents the number of ways to form that particular sum using the candidates. The approach involves iterating through candidates and updating the DP array for each possible sum that can be formed with that candidate.
def combinationSum(candidates, target):
dp = [[] for _ in range(target + 1)]
dp[0] = [[]]
for candidate in candidates:
for i in range(candidate, target + 1):
for sublist in dp[i - candidate]:
dp[i].append(sublist + [candidate])
return dp[target]
candidates = [2, 3, 6, 7]
target = 7
print(combinationSum(candidates, target))import java.util.ArrayList;
import java.util.List;
public class CombinationSumDP {
public static List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>>[] dp = new List[target + 1];
dp[0] = new ArrayList<>();
dp[0].add(new ArrayList<>());
for (int i = 1; i <= target; i++) {
dp[i] = new ArrayList<>();
for (int candidate : candidates) {
if (i >= candidate) {
for (List<Integer> combination : dp[i - candidate]) {
List<Integer> newComb = new ArrayList<>(combination);
newComb.add(candidate);
dp[i].add(newComb);
}
}
}
}
return dp[target];
}
public static void main(String[] args) {
int[] candidates = {2, 3, 6, 7};
int target = 7;
List<List<Integer>> results = combinationSum(candidates, target);
results.forEach(System.out::println);
}
}#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> dp[target + 1];
dp[0] = {{}}; // Base condition
for (int i = 1; i <= target; i++) {
for (const int& cand : candidates) {
if (i >= cand) {
for (auto& subResult : dp[i - cand]) {
dp[i].push_back(subResult);
dp[i].back().push_back(cand);
}
}
}
}
return dp[target];
}
int main() {
vector<int> candidates = {2, 3, 6, 7};
int target = 7;
vector<vector<int>> result = combinationSum(candidates, target);
for (const auto& comb : result) {
cout << "[";
for (int i = 0; i < comb.size(); ++i) {
cout << comb[i] << (i == comb.size() - 1 ? "" : ", ");
}
cout << "]\n";
}
return 0;
}const combinationSum = function(candidates, target) {
const dp = Array.from({ length: target + 1 }, () => []);
dp[0] = [[]];
for (const candidate of candidates) {
for (let i = candidate; i <= target; i++) {
for (const comb of dp[i - candidate]) {
dp[i].push([...comb, candidate]);
}
}
}
return dp[target];
};
const candidates = [2, 3, 6, 7];
const target = 7;
console.log(combinationSum(candidates, target));#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
bool combinationSumHelper(int *candidates, int candidatesSize, int target, int **dp) {
if (target == 0) return true;
if (target < 0) return false;
if (dp[target] != NULL) return true;
for (int i = 0; i < candidatesSize; i++) {
if (combinationSumHelper(candidates, candidatesSize, target - candidates[i], dp)) {
dp[target] = candidates;
return true;
}
}
return false;
}
int **combinationSum(int *candidates, int candidatesSize, int target, int *returnSize, int **returnColumnSizes) {
int **dp = (int **)calloc(target + 1, sizeof(int *));
*returnSize = 0;
combinationSumHelper(candidates, candidatesSize, target, dp);
*returnColumnSizes = (int *)malloc(sizeof(int) * (*returnSize));
// Dummy return, as the full implementation of DP building combinations is complex in C.
return dp;
}
int main() {
int candidates[] = {2, 3, 6, 7};
int target = 7;
int *returnSize, *returnColumnSizes;
int **result = combinationSum(candidates, 4, target, returnSize, &returnColumnSizes);
// Assume combination finding has been done, here we would print results.
free(returnColumnSizes);
return 0;
}using System;
using System.Collections.Generic;
class CombinationSumDPSolution {
public IList<IList<int>> CombinationSum(int[] candidates, int target) {
List<IList<int>>[] dp = new List<IList<int>>[target + 1];
dp[0] = new List<IList<int>> { new List<int>() };
for (int i = 1; i <= target; i++) {
dp[i] = new List<IList<int>>();
foreach (int candidate in candidates) {
if (i >= candidate) {
foreach (var combination in dp[i - candidate]) {
var newComb = new List<int>(combination);
newComb.Add(candidate);
dp[i].Add(newComb);
}
}
}
}
return dp[target];
}
static void Main(string[] args) {
int[] candidates = {2, 3, 6, 7};
int target = 7;
CombinationSumDPSolution solution = new CombinationSumDPSolution();
var result = solution.CombinationSum(candidates, target);
foreach (var combination in result) {
Console.WriteLine("[" + string.Join(", ", combination) + "]");
}
}
}The Python implementation uses a dynamic programming step-up approach where each candidate helps form every possible sum from itself up to the target by utilizing previous built combination lists at dp indices.
Time Complexity: O(T * N), each dp entry updated with available candidates.
Space Complexity: O(T).
Approach 3: Sorting + Pruning + Backtracking
We can first sort the array to facilitate pruning.
Next, we design a function dfs(i, s), which means starting the search from index i with a remaining target value of s. Here, i and s are both non-negative integers, the current search path is t, and the answer is ans.
In the function dfs(i, s), we first check whether s is 0. If it is, we add the current search path t to the answer ans, and then return. If s \lt candidates[i], it means that the elements of the current index and the following indices are all greater than the remaining target value s, and the path is invalid, so we return directly. Otherwise, we start the search from index i, and the search index range is j \in [i, n), where n is the length of the array candidates. During the search, we add the element of the current index to the search path t, recursively call the function dfs(j, s - candidates[j]), and after the recursion ends, we remove the element of the current index from the search path t.
In the main function, we just need to call the function dfs(0, target) to get the answer.
The time complexity is O(2^n times n), and the space complexity is O(n). Here, n is the length of the array candidates. Due to pruning, the actual time complexity is much less than O(2^n times n).
Similar problems:
function combinationSum(candidates: number[], target: number): number[][] {
candidates.sort((a, b) => a - b);
const ans: number[][] = [];
const t: number[] = [];
const dfs = (i: number, s: number) => {
if (s === 0) {
ans.push(t.slice());
return;
}
if (s < candidates[i]) {
return;
}
for (let j = i; j < candidates.length; ++j) {
t.push(candidates[j]);
dfs(j, s - candidates[j]);
t.pop();
}
};
dfs(0, target);
return ans;
}func combinationSum(candidates []int, target int) (ans [][]int) {
sort.Ints(candidates)
t := []int{}
var dfs func(i, s int)
dfs = func(i, s int) {
if s == 0 {
ans = append(ans, slices.Clone(t))
return
}
if s < candidates[i] {
return
}
for j := i; j < len(candidates); j++ {
t = append(t, candidates[j])
dfs(j, s-candidates[j])
t = t[:len(t)-1]
}
}
dfs(0, target)
return
}impl Solution {
fn dfs(i: usize, s: i32, candidates: &Vec<i32>, t: &mut Vec<i32>, ans: &mut Vec<Vec<i32>>) {
if s == 0 {
ans.push(t.clone());
return;
}
if s < candidates[i] {
return;
}
for j in i..candidates.len() {
t.push(candidates[j]);
Self::dfs(j, s - candidates[j], candidates, t, ans);
t.pop();
}
}
pub fn combination_sum(mut candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
candidates.sort();
let mut ans = Vec::new();
Self::dfs(0, target, &candidates, &mut vec![], &mut ans);
ans
}
}Approach 4: Sorting + Pruning + Backtracking(Another Form)
We can also change the implementation logic of the function dfs(i, s) to another form. In the function dfs(i, s), we first check whether s is 0. If it is, we add the current search path t to the answer ans, and then return. If i geq n or s \lt candidates[i], the path is invalid, so we return directly. Otherwise, we consider two situations, one is not selecting the element of the current index, that is, recursively calling the function dfs(i + 1, s), and the other is selecting the element of the current index, that is, recursively calling the function dfs(i, s - candidates[i]).
The time complexity is O(2^n times n), and the space complexity is O(n). Here, n is the length of the array candidates. Due to pruning, the actual time complexity is much less than O(2^n times n).
function combinationSum(candidates: number[], target: number): number[][] {
candidates.sort((a, b) => a - b);
const ans: number[][] = [];
const t: number[] = [];
const dfs = (i: number, s: number) => {
if (s === 0) {
ans.push(t.slice());
return;
}
if (i >= candidates.length || s < candidates[i]) {
return;
}
dfs(i + 1, s);
t.push(candidates[i]);
dfs(i, s - candidates[i]);
t.pop();
};
dfs(0, target);
return ans;
}func combinationSum(candidates []int, target int) (ans [][]int) {
sort.Ints(candidates)
t := []int{}
var dfs func(i, s int)
dfs = func(i, s int) {
if s == 0 {
ans = append(ans, slices.Clone(t))
return
}
if i >= len(candidates) || s < candidates[i] {
return
}
dfs(i+1, s)
t = append(t, candidates[i])
dfs(i, s-candidates[i])
t = t[:len(t)-1]
}
dfs(0, target)
return
}impl Solution {
fn dfs(i: usize, s: i32, candidates: &Vec<i32>, t: &mut Vec<i32>, ans: &mut Vec<Vec<i32>>) {
if s == 0 {
ans.push(t.clone());
return;
}
if i >= candidates.len() || s < candidates[i] {
return;
}
Self::dfs(i + 1, s, candidates, t, ans);
t.push(candidates[i]);
Self::dfs(i, s - candidates[i], candidates, t, ans);
t.pop();
}
pub fn combination_sum(mut candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
candidates.sort();
let mut ans = Vec::new();
Self::dfs(0, target, &candidates, &mut vec![], &mut ans);
ans
}
}class Solution {
/**
* @param integer[] $candidates
* @param integer $target
* @return integer[][]
*/
function combinationSum($candidates, $target) {
$result = [];
$currentCombination = [];
$startIndex = 0;
sort($candidates);
$this->findCombinations($candidates, $target, $startIndex, $currentCombination, $result);
return $result;
}
function findCombinations($candidates, $target, $startIndex, $currentCombination, &$result) {
if ($target === 0) {
$result[] = $currentCombination;
return;
}
for ($i = $startIndex; $i < count($candidates); $i++) {
$num = $candidates[$i];
if ($num > $target) {
break;
}
$currentCombination[] = $num;
$this->findCombinations($candidates, $target - $num, $i, $currentCombination, $result);
array_pop($currentCombination);
}
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Backtracking Approach | Time Complexity: O(2^T), since multiple paths can be explored. |
| Dynamic Programming Approach | Time Complexity: O(T * N), each dp entry updated with available candidates. |
| Sorting + Pruning + Backtracking | – |
| Sorting + Pruning + Backtracking(Another Form) | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking | Exponential (≈ O(2^T)) | O(T) | Standard interview solution when generating all valid combinations |
| Dynamic Programming | O(n * target * k) | O(target * k) | When you want a bottom-up construction of combinations or reuse intermediate sums |
Frequently asked questions
Is Combination Sum easy or hard?
Combination Sum is generally classified as a medium-level problem. The recursion pattern is straightforward, but controlling duplicates, pruning branches, and correctly structuring backtracking requires solid understanding of recursive search.
How to solve Combination Sum in O(n)?
Combination Sum cannot be solved in strict O(n) time because the output itself may contain many combinations. Any algorithm must enumerate all valid sets that sum to the target. The best practical approaches are exponential backtracking or dynamic programming that builds combinations up to the target.
What is the best approach for Combination Sum?
Backtracking is the most common and expected solution. It recursively builds combinations, subtracting candidate values from the remaining target and stopping when the target reaches zero. This method efficiently explores possibilities while pruning invalid branches. Time complexity is exponential but practical because pruning eliminates many paths.
What data structure is used in Combination Sum?
The core structure is an array of candidate numbers combined with recursion and a dynamic list to store the current path. Backtracking uses a stack-like recursion call stack to explore combinations. Dynamic programming variants use arrays or lists of lists to store combinations for each intermediate sum.
What is the time complexity of Combination Sum?
The typical backtracking solution runs in exponential time, often approximated as O(2^T) depending on the target value and smallest candidate number. Each recursive call explores including or excluding candidates while building combinations. Space complexity is O(T) for the recursion stack and current combination.
Combination Sum Python or Java solution approach?
Both Python and Java implementations typically use recursive backtracking. A helper function tracks the remaining target, current index, and the current combination list. When the remaining target becomes zero, the combination is added to the result set.
Is Combination Sum asked at Google, Amazon, or Meta?
Combination Sum frequently appears in coding interviews at major tech companies including Amazon, Google, Meta, and Microsoft. Interviewers use it to evaluate recursion, backtracking, pruning strategies, and understanding of search trees.