Log inSign up
mediumLeetCodeNot Started

Combination Sum II

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

Backtracking
Solve on LeetCode
Lesson

Problem Statement

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.

Each number in candidates may only be used once in the combination.

Note: The solution set must not contain duplicate combinations.

Example 1 · Duplicates in Candidates with Target 8:

Input: candidates = [10, 1, 2, 7, 6, 1, 5], target = 8
Output: [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]
Explanation: After sorting [1, 1, 2, 5, 6, 7, 10], unique combinations summing to 8 are generated without duplicates.

Example 2 · All Twos with Target 5:

Input: candidates = [2, 5, 2, 1, 2], target = 5
Output: [[1, 2, 2], [5]]
Explanation: 1+2+2 = 5 and 5 = 5.

Constraints:

  • 1 <= candidates.length <= 100
  • 1 <= candidates[i] <= 50
  • 1 <= target <= 30

What You'll Learn

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

  • Understand the distinction between duplicates at the same recursion level vs across different recursion levels.
  • Master the i > start && candidates[i] == candidates[i - 1] deduplication pattern.
  • Optimize backtracking search with early loop termination (break).

Pattern Recognition Trigger

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

Signals to Look For:

  • Input contains duplicate elements
  • Each element can be used at most once
  • Result must contain only unique combinations without duplicates

Algorithmic Decision Tree:

  • Always sort candidates before running recursion.
  • In the backtracking loop for i from start to n - 1: if i > start && candidates[i] === candidates[i - 1], skip with continue.
  • Advance index to i + 1 on recursive calls to enforce single usage.

Connected Patterns:

Combination SumSubsets IIPermutations II

1. Generate All Combinations + Hash Set Deduplication

Intuition

Recurse on each element with Pick/Don't Pick decisions. When a subset sums to target, sort it and insert into a Hash Set of vectors/strings to filter duplicates. Returns all unique sets.

When to apply: Naive baseline to demonstrate why dedicated branch deduplication is necessary.

Algorithm

  1. Sort candidates.
  2. Perform standard Pick/Don't Pick recursion moving index + 1 at each step.
  3. When target == 0, serialize or sort current and insert into std::set / HashSet.
  4. Convert set back to 2D list.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <set>
4#include <algorithm>
5
6using namespace std;
7
8class Solution {
9 void solve(int index, int target, vector<int>& candidates, vector<int>& current, set<vector<int>>& uniqueCombs) {
10 if (target == 0) {
11 uniqueCombs.insert(current);
12 return;
13 }
14 if (index == candidates.size() || target < 0) return;
15
16 // Choice 1: Pick
17 current.push_back(candidates[index]);
18 solve(index + 1, target - candidates[index], candidates, current, uniqueCombs);
19 current.pop_back();
20
21 // Choice 2: Don't Pick
22 solve(index + 1, target, candidates, current, uniqueCombs);
23 }
24
25public:
26 vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
27 sort(candidates.begin(), candidates.end());
28 set<vector<int>> uniqueCombs;
29 vector<int> current;
30 solve(0, target, candidates, current, uniqueCombs);
31 return vector<vector<int>>(uniqueCombs.begin(), uniqueCombs.end());
32 }
33};
34
35int main() {
36 Solution sol;
37 vector<int> candidates = {10, 1, 2, 7, 6, 1, 5};
38 auto res = sol.combinationSum2(candidates, 8);
39 for (const auto& c : res) {
40 cout << "[ ";
41 for (int v : c) cout << v << " ";
42 cout << "] ";
43 }
44 cout << endl;
45 return 0;
46}

Time & Space Complexity

  • Time complexity: O(2^N * K log K) — Generates all 2N subset combinations, and hashes/sorts each combination of length K.
  • Space complexity: O(2^N * K) — Hash Set stores all generated combinations before duplicate elimination.

2. Frequency Map Grouping Recursion

Intuition

Count frequencies of distinct candidates. Recurse over distinct numbers: for a number with count C, loop k from 0 to C, add k copies to current path, and recurse to next distinct number.

When to apply: When candidates have heavy duplicate multiplicity.

Algorithm

  1. Create frequency map of candidates.
  2. Extract distinct numbers list keys and counts.
  3. Define solve(keyIndex, target):
  4. - For k from 0 to count[keys[keyIndex]]:
  5. - If k * keys[keyIndex] <= target, append k copies and recurse to keyIndex + 1.
  6. - Backtrack by popping k elements.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <map>
4
5using namespace std;
6
7class Solution {
8 void backtrack(int idx, int target, const vector<pair<int, int>>& freq, vector<int>& current, vector<vector<int>>& result) {
9 if (target == 0) {
10 result.push_back(current);
11 return;
12 }
13 if (idx == freq.size() || target < 0) return;
14
15 int val = freq[idx].first;
16 int count = freq[idx].second;
17
18 // Try using 0 to count instances of val
19 backtrack(idx + 1, target, freq, current, result);
20
21 for (int k = 1; k <= count && k * val <= target; k++) {
22 current.push_back(val);
23 backtrack(idx + 1, target - k * val, freq, current, result);
24 }
25 for (int k = 1; k <= count && k * val <= target; k++) {
26 current.pop_back();
27 }
28 }
29
30public:
31 vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
32 map<int, int> counts;
33 for (int x : candidates) counts[x]++;
34 vector<pair<int, int>> freq(counts.begin(), counts.end());
35 vector<vector<int>> result;
36 vector<int> current;
37 backtrack(0, target, freq, current, result);
38 return result;
39 }
40};
41
42int main() {
43 Solution sol;
44 vector<int> candidates = {10, 1, 2, 7, 6, 1, 5};
45 auto res = sol.combinationSum2(candidates, 8);
46 for (const auto& c : res) {
47 cout << "[ ";
48 for (int v : c) cout << v << " ";
49 cout << "] ";
50 }
51 cout << endl;
52 return 0;
53}

Time & Space Complexity

  • Time complexity: O(2^N * K) — Explores valid frequency choices directly, avoiding generating duplicate permutations.
  • Space complexity: O(N) — Stack depth bounded by number of distinct candidates.

3. In-Place Sorted Backtracking with Level Duplicate Pruning (Optimal)

Intuition

Sorting brings identical numbers together. In the loop at recursion depth d, candidates[start] is the first candidate tested. If i > start and candidates[i] == candidates[i - 1], exploring candidates[i] would generate a subset of combinations already generated by candidates[i - 1]. Skipping it with continue eliminates duplicate paths at zero memory overhead.

When to apply: The standard gold-standard interview implementation.

Algorithm

  1. Sort candidates in ascending order.
  2. Define backtrack(start, target, current):
  3. - If target == 0, append copy of current to result and return.
  4. - Loop i from start to candidates.length - 1:
  5. - If candidates[i] > target, break (early pruning).
  6. - If i > start && candidates[i] == candidates[i - 1], continue (skip duplicate at this level).
  7. - Push candidates[i] to current.
  8. - Recurse backtrack(i + 1, target - candidates[i], current).
  9. - Pop candidates[i] from current.
  10. Return result.

Duplicate Pruning State Trace

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
Sorted array is [1, 1, 2, 5, 6, 7, 10]
Visual state
Values and pointers at this exact step
tree
Root
rem: 8, path: []

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

Variables at this step
target
8
start
0
current
[]
Why this step matters

Sorted array is [1, 1, 2, 5, 6, 7, 10]. Root state: target = 8, start = 0.

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
16 if (candidates[i] > target) break;
17
18 // Skip duplicate choices at the same recursion depth
19 if (i > start && candidates[i] == candidates[i - 1]) continue;
20
21 current.push_back(candidates[i]);
22 backtrack(i + 1, target - candidates[i], candidates, current, result); // i + 1 since single-use
23 current.pop_back(); // backtrack
24 }
25 }
26
27public:
28 vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
29 sort(candidates.begin(), candidates.end());
30 vector<vector<int>> result;
31 vector<int> current;
32 backtrack(0, target, candidates, current, result);
33 return result;
34 }
35};
36
37int main() {
38 Solution sol;
39 vector<int> candidates = {10, 1, 2, 7, 6, 1, 5};
40 int target = 8;
41 auto res = sol.combinationSum2(candidates, target);
42 for (const auto& comb : res) {
43 cout << "[ ";
44 for (int v : comb) cout << v << " ";
45 cout << "] ";
46 }
47 cout << endl;
48 return 0;
49}

Time & Space Complexity

  • Time complexity: O(2^N * K) — Every element is considered at most once per path, bounded by 2N total subsets. K is average combination length.
  • Space complexity: O(N) — Recursion call stack depth is bounded by N (the number of candidates).

Approach Comparison Matrix

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

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Generate All + Set DeduplicationO(2^N * K log K)O(2^N * K)Generate all subset paths and filter duplicates via HashSet.HashSet storage of duplicate paths
2.Frequency Map Grouping RecursionO(2^N * K)O(N)Count frequencies of distinct numbers and recurse over multiplicities.Frequency table management
3.In-Place Sorted Backtracking with Level Duplicate PruningOptimalO(2^N * K)O(N)Sort + i > start && candidates[i] == candidates[i-1] level skipping.Combinatorial branch exploration

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Writing i > 0 instead of i > start in the duplicate check (which wrongly disables picking identical numbers at deeper levels, preventing [1, 1]).

Pitfall 2:

Calling backtrack(i, ...) instead of backtrack(i + 1, ...) allowing infinite reuse of the same element.

Pitfall 3:

Forgetting to sort candidates before running the backtracking algorithm.

Crucial Edge Cases to Validate:

  • All Elements Identical: candidates = [1, 1, 1, 1], target = 2 -> returns [[1, 1]].
  • No Valid Combination: candidates = [3, 5], target = 4 -> returns [].
  • Single Element Matches: candidates = [7], target = 7 -> returns [[7]].
  • Large Target: candidates = [1, 2], target = 10 -> returns [].

Interview Tips & Best Practices

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

  1. Emphasize the difference between vertical recursion depth (reusing a duplicate from input) vs horizontal loop breadth (skipping duplicate branch).
  2. Write out the [1, 1, 2] tree on whiteboard to illustrate why i > start works cleanly.

Quick Comprehension Check

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

1.Why does i > start && candidates[i] == candidates[i - 1] allow [1, 1] to be generated while preventing duplicate combinations?

2.What is the key difference between Combination Sum I and Combination Sum II in the recursive step?

Back to DSA Sheet