Log inSign up
mediumLeetCodeNot Started

Combination Sum

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

Backtracking
Solve on LeetCode
Lesson

Problem Statement

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 · Standard Target Combination:

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 · Multiple Multi-use Combinations:

Input: candidates = [2, 3, 5], target = 8
Output: [[2, 2, 2, 2], [2, 3, 3], [3, 5]]
Explanation: 2+2+2+2 = 8, 2+3+3 = 8, 3+5 = 8.

Example 3 · No Valid Combination:

Input: candidates = [2], target = 1
Output: []
Explanation: The minimum element is 2 which is already larger than target 1.

Constraints:

  • 1 <= candidates.length <= 30
  • 2 <= candidates[i] <= 40
  • All elements of candidates are distinct.
  • 1 <= target <= 40

What You'll Learn

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

  • Master the Pick/Don't Pick recursion paradigm with element reuse.
  • Understand why staying at index i allows unbounded repetition while preventing duplicate permutations.
  • Implement backtracking state unwinding cleanly across C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

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

Signals to Look For:

  • Find all combinations summing to a target value
  • Elements can be reused unlimited times
  • Output must contain only unique combinations without duplicates

Algorithmic Decision Tree:

  • Use Backtracking recursion with state (index, target, currentCombination).
  • If candidates[i] <= target, append candidates[i] and recurse with same index i and target - candidates[i].
  • Backtrack: pop the appended element, then advance loop or explore the exclusion branch.

Connected Patterns:

Combination Sum IICombination Sum IIICoin ChangeSubsets

1. Binary Choice State Recursion (Pick vs Not Pick)

Intuition

Define solve(index, target, current). Base case: if index == n, check if target == 0 and record solution. Recursive branches: (1) Pick branch: if candidates[index] <= target, push candidate and call solve(index, target - candidates[index], current). (2) Don't Pick branch: pop candidate and call solve(index + 1, target, current).

When to apply: Great for conceptual clarity and constructing recursion trees directly.

Algorithm

  1. Base case 1: If index == candidates.length, if target == 0 add copy of current to result; return.
  2. Pick choice: If candidates[index] <= target, push candidates[index], call solve(index, target - candidates[index]), and pop candidates[index].
  3. Not-Pick choice: Call solve(index + 1, target).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class Solution {
7 void solve(int index, int target, vector<int>& candidates, vector<int>& current, vector<vector<int>>& result) {
8 if (index == candidates.size()) {
9 if (target == 0) {
10 result.push_back(current);
11 }
12 return;
13 }
14
15 // Choice 1: Pick
16 if (candidates[index] <= target) {
17 current.push_back(candidates[index]);
18 solve(index, target - candidates[index], candidates, current, result);
19 current.pop_back(); // backtrack
20 }
21
22 // Choice 2: Don't Pick
23 solve(index + 1, target, candidates, current, result);
24 }
25
26public:
27 vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
28 vector<vector<int>> result;
29 vector<int> current;
30 solve(0, target, candidates, current, result);
31 return result;
32 }
33};
34
35int main() {
36 Solution sol;
37 vector<int> candidates = {2, 3, 6, 7};
38 int target = 7;
39 auto res = sol.combinationSum(candidates, target);
40 for (const auto& comb : res) {
41 cout << "[ ";
42 for (int v : comb) cout << v << " ";
43 cout << "] ";
44 }
45 cout << endl;
46 return 0;
47}

Time & Space Complexity

  • Time complexity: O(2^T * K) — T is target value. In worst case (smallest candidate = 2), tree depth is T/2. K is average length of each combination copied.
  • Space complexity: O(T / min_val) — Maximum recursion depth is target / min(candidates) frames.

2. For-Loop Backtracking with Pruning

Intuition

Instead of explicit Pick/Don't Pick branching, use a loop starting from start index. For each i from start to n - 1: push candidates[i], recurse with i and target - candidates[i], and backtrack by popping.

When to apply: Standard template for subset/combination backtracking problems.

Algorithm

  1. If target == 0, add copy of current to result and return.
  2. If target < 0, return.
  3. Loop i from start to candidates.length - 1:
  4. - Push candidates[i] to current.
  5. - Recurse backtrack(i, target - candidates[i], current).
  6. - Pop candidates[i] from current.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class Solution {
7 void backtrack(int start, int target, vector<int>& candidates, vector<int>& current, vector<vector<int>>& result) {
8 if (target == 0) {
9 result.push_back(current);
10 return;
11 }
12 if (target < 0) return;
13
14 for (int i = start; i < candidates.size(); i++) {
15 current.push_back(candidates[i]);
16 backtrack(i, target - candidates[i], candidates, current, result);
17 current.pop_back();
18 }
19 }
20
21public:
22 vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
23 vector<vector<int>> result;
24 vector<int> current;
25 backtrack(0, target, candidates, current, result);
26 return result;
27 }
28};
29
30int main() {
31 Solution sol;
32 vector<int> candidates = {2, 3, 6, 7};
33 auto res = sol.combinationSum(candidates, 7);
34 for (const auto& comb : res) {
35 cout << "[ ";
36 for (int v : comb) cout << v << " ";
37 cout << "] ";
38 }
39 cout << endl;
40 return 0;
41}

Time & Space Complexity

  • Time complexity: O(2^T * K) — Generates all valid combinations with branching factor proportional to available candidate numbers.
  • Space complexity: O(T / min_val) — Auxiliary space corresponds to the recursion call stack depth.

3. Sorted Backtracking with Early Branch Pruning (Optimal)

Intuition

By sorting candidates in ascending order, if candidates[i] > remaining_target, then all subsequent candidates candidates[j] (where j > i) will also exceed the target. We can immediately break the loop, pruning the entire subtree.

When to apply: The industry standard optimal solution for combination search problems.

Algorithm

  1. Sort candidates in ascending order O(N log N).
  2. Define backtrack(start, target, current):
  3. - If target == 0, append a copy of current to result and return.
  4. - Iterate i from start to candidates.length - 1:
  5. - If candidates[i] > target, break immediately (pruning step).
  6. - Push candidates[i] to current.
  7. - Recurse backtrack(i, target - candidates[i], current).
  8. - Pop candidates[i] from current.
  9. Return result.

Decision Tree State Trace

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

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

Variables at this step
target
7
currentPath
[]
candidateIndex
0
Why this step matters

Start at root with target = 7, start = 0, current = [].

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8 void backtrack(int start, int target, vector<int>& candidates, vector<int>& current, vector<vector<int>>& result) {
9 if (target == 0) {
10 result.push_back(current);
11 return;
12 }
13
14 for (int i = start; i < candidates.size(); i++) {
15 // Early pruning: since candidates is sorted, subsequent elements are also > target
16 if (candidates[i] > target) break;
17
18 current.push_back(candidates[i]);
19 backtrack(i, target - candidates[i], candidates, current, result);
20 current.pop_back(); // backtrack
21 }
22 }
23
24public:
25 vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
26 sort(candidates.begin(), candidates.end());
27 vector<vector<int>> result;
28 vector<int> current;
29 backtrack(0, target, candidates, current, result);
30 return result;
31 }
32};
33
34int main() {
35 Solution sol;
36 vector<int> candidates = {2, 3, 6, 7};
37 int target = 7;
38 auto res = sol.combinationSum(candidates, target);
39 for (const auto& comb : res) {
40 cout << "[ ";
41 for (int v : comb) cout << v << " ";
42 cout << "] ";
43 }
44 cout << endl;
45 return 0;
46}

Time & Space Complexity

  • Time complexity: O(2^T * K) — Pruning dramatically reduces constant factor and avoids exploring all fruitless branches where candidate exceeds remaining sum.
  • Space complexity: O(T / min_val) — Recursion depth is bounded by target / candidates[0].

Approach Comparison Matrix

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

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Binary Choice State RecursionO(2^T * K)O(T / min_val)Explicit Pick and Don't Pick binary decisions at each candidate index.Binary tree recursion depth
2.For-Loop Backtracking with PruningO(2^T * K)O(T / min_val)Iterate from start index in loop, reducing recursion frame count.Unsorted candidate checks
3.Sorted Backtracking with Early Branch PruningOptimalO(2^T * K)O(T / min_val)Sort candidates upfront and break loop immediately when candidates[i] > target.Combinatorial state count

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Passing i + 1 instead of i when recursing, accidentally preventing element reuse.

Pitfall 2:

Not creating a new copy/clone of the current list when adding to result (resulting in empty lists after backtracking).

Pitfall 3:

Forgetting to pop/backtrack the appended element after the recursive call returns.

Pitfall 4:

Using continue instead of break after sorting (losing the benefit of early pruning).

Crucial Edge Cases to Validate:

  • Target Smaller than Smallest Candidate: candidates = [5], target = 3 -> returns [] immediately.
  • Target Equal to Single Candidate: candidates = [7], target = 7 -> returns [[7]].
  • Repeated Same Element: candidates = [2], target = 6 -> returns [[2, 2, 2]].
  • Multiple Paths to Same Target: candidates = [2, 3, 5], target = 8 -> returns [[2, 2, 2, 2], [2, 3, 3], [3, 5]].

Interview Tips & Best Practices

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

  1. Clarify whether candidates contain negatives or zeroes (if 0 or negative numbers are allowed, combinations can be infinite).
  2. Highlight why sorting + break turns O(2T) exponential search into a highly optimized search.
  3. Always discuss copy-by-value vs reference when appending current path to result list.

Quick Comprehension Check

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

1.Why does calling backtrack(i, target - candidates[i]) (with index i rather than i + 1) avoid generating duplicate permutations like [2, 3, 2]?

2.What enables early pruning with break in the optimal approach?

Back to DSA Sheet