Combination Sum II — Solution in Python, Java & C++
Combination Sum II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Combination Sum II is a medium coding problem on arrays and backtracking, asked in Amazon, Meta and LinkedIn interviews.
- Difficulty: Medium
- Topics: Arrays, Backtracking
- Asked at: Amazon, Meta, LinkedIn
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a list of positive integers candidates (values may repeat) and a positive target. Return every distinct combination of candidates whose values add up to exactly target. Each position of candidates may be used at most once in a combination, so a value can appear in a combination at most as many times as it appears in the input.
Two combinations are the same if they hold the same values with the same multiplicities; list each only once. Write each combination in non-decreasing order and list the combinations in lexicographic order. If there is none, return an empty list.
Example 1
Input: candidates = [3,1,4,1,5,2], target = 6
Output: [[1,1,4],[1,2,3],[1,5],[2,4]]
Example 2
Input: candidates = [2,2,2,2], target = 5
Output: []
Explanation: Sums of 2s are always even.
Example 3
Input: candidates = [4,2,6], target = 6
Output: [[2,4],[6]]
Constraints
1 <= candidates.length <= 1001 <= candidates[i] <= 501 <= target <= 30
Hints for Combination Sum II
Hint 1
Sort the candidates. Once a candidate exceeds what is left of the target, so does every later one.
Hint 2
Choose the next element of the combination by index, always moving forward so each position is used at most once.
Hint 3
To avoid duplicate combinations, at a single recursion depth use each distinct value once: skip
iwheni > startandcandidates[i] == candidates[i - 1].
How to solve Combination Sum II
This is Subsets II restricted to subsets with the right sum: after sorting, skipping repeated values at the same depth makes each combination appear once, and the positive values let the search stop early.
Approach
- Sort
candidates. dfs(start, remaining): ifremaining == 0, record a copy of the path.- Otherwise for
ifromstart: skip duplicates at this depth; ifcandidates[i] > remaining, stop the loop; else push it, calldfs(i + 1, remaining - candidates[i]), pop. - Return what was recorded.
Why it works
Moving to i + 1 uses each position at most once, and the duplicate skip lets only the leftmost copy of a value start a branch at a given depth, so each multiset is built exactly once. Values are tried in increasing order at every depth, and no combination is a prefix of another (all have the same positive sum), so the output comes out lexicographically sorted.
Complexity
- Time —
O(2^n · n) in the worst case; the sum bound prunes most branches - Space —
O(target) recursion depth besides the output
Pitfalls
- Recursing on
iinstead ofi + 1reuses the same position (that is Combination Sum I). breakrather thancontinuewhen a value is too big — the array is sorted, so the rest are too big as well.- Return an empty list, not
[[]], when nothing sums to the target.
Reference solution
Python
from typing import List
def combinationSum2(candidates: List[int], target: int) -> List[List[int]]:
a = sorted(candidates)
out = []
path = []
def dfs(start, rem):
if rem == 0:
out.append(path[:])
return
for i in range(start, len(a)):
if i > start and a[i] == a[i - 1]:
continue
if a[i] > rem:
break
path.append(a[i])
dfs(i + 1, rem - a[i])
path.pop()
dfs(0, target)
return outJava
public static int[][] combinationSum2(int[] candidates, int target) {
int[] a = candidates.clone();
Arrays.sort(a);
List<int[]> out = new ArrayList<>();
comboDfs(a, 0, target, new int[a.length], 0, out);
return out.toArray(new int[0][]);
}
static void comboDfs(int[] a, int start, int rem, int[] path, int len, List<int[]> out) {
if (rem == 0) {
out.add(Arrays.copyOf(path, len));
return;
}
for (int i = start; i < a.length; i++) {
if (i > start && a[i] == a[i - 1]) continue;
if (a[i] > rem) break;
path[len] = a[i];
comboDfs(a, i + 1, rem - a[i], path, len + 1, out);
}
}C++
void comboDfs(vector<int>& a, int start, int rem, vector<int>& path, vector<vector<int>>& out) {
if (rem == 0) {
out.push_back(path);
return;
}
for (int i = start; i < (int)a.size(); i++) {
if (i > start && a[i] == a[i - 1]) continue;
if (a[i] > rem) break;
path.push_back(a[i]);
comboDfs(a, i + 1, rem - a[i], path, out);
path.pop_back();
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<int> a(candidates.begin(), candidates.end());
sort(a.begin(), a.end());
vector<vector<int>> out;
vector<int> path;
comboDfs(a, 0, target, path, out);
return out;
}JavaScript
var combinationSum2 = function(candidates, target) {
var a = candidates.slice().sort(function(x, y) { return x - y; });
var out = [];
var path = [];
var dfs = function(start, rem) {
if (rem === 0) {
out.push(path.slice());
return;
}
for (var i = start; i < a.length; i++) {
if (i > start && a[i] === a[i - 1]) continue;
if (a[i] > rem) break;
path.push(a[i]);
dfs(i + 1, rem - a[i]);
path.pop();
}
};
dfs(0, target);
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Backtracking