Difficulty: MediumBacktracking

Combination Sum II

Problem in Plain English

Given candidates that may repeat and a target, return every unique combination summing to the target while spending each element at most once. Duplicate combinations appear only once.

Problem Statement

Given a collection of candidate numbers candidates that may hold duplicates, plus an integer target, return every unique combination whose values sum to target.

Each element may be used at most once, so two equal values at different positions are still two separate one-time picks.

The answer must contain no duplicate combinations; return it in any order.

Constraints

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

Examples

Example 1

Input: candidates = [10,1,2,7,6,1,5], target = 8
Output: [[1,1,6],[1,2,5],[1,7],[2,6]]

The four listed combinations sum to 8. Both 1s are needed for [1,1,6]; either 1 can form [1,7], but those choices describe the same value combination and appear once. The value 10 is too large.

Example 2

Input: candidates = [2,5,2,1,2], target = 5
Output: [[1,2,2],[5]]

Using 1 and two separate 2 positions makes [1,2,2]; the lone 5 makes [5]. The three possible ways to choose two of the three 2s collapse to one value combination.

Example 3

Input: candidates = [1], target = 2
Output: []

The only available value is 1. Reusing it would make 2, but each position can be used once, so no valid combination exists.

Intuition

Equal values are interchangeable as answers, but their positions are separate resources. Example 1 contains two 1s, so [1,1,6] is legal, while choosing either 1 for [1,7] must produce only one answer. Backtracking builds a partial combination and undoes each choice. Sorting lets us skip equal alternatives at the same decision level while still using a second equal value deeper in the path.

Approaches

Subset Filter + Dedup

Solution Details

Reveal Subset Filter + Dedup: intuition, complexity, and code

Intuition

Try taking or skipping each position, keeping only paths that reach the target. Equal values at different positions create repeated answers; sorting a successful path gives a canonical key so a set can remove those repetitions. Positive values let a branch stop as soon as its sum reaches or exceeds the target.

Step-by-Step Logic

Start with index i = 0, total = 0, an empty path and an empty set of successful keys. At each index, explore taking that position first, then undo it and explore skipping it.
Stop a branch when total exceeds target or all positions are exhausted. In Example 1, taking the first value 10 gives total 10, so that entire branch is pruned.
When total equals target, sort a copy of the path and insert its key if unseen, then return. After skipping 10, taking values 1, 2, skipping 7 and 6, then taking 1 and 5 produces [1,2,1,5] with total 9 and is pruned; skipping the second 1 instead produces [1,2,5] with total 8.
Restore the path after every take branch before exploring its skip branch. Selecting the other 1 later can also make [1,2,5], but the canonical key is already present.
Continue until both choices at every reachable index are resolved. Example 1 returns the four combinations [1,1,6], [1,2,5], [1,7] and [2,6], in any order.

Why It Works

At index i, the path contains exactly the selected positions before i, and total is their sum. Taking position i or skipping it covers every legal subset, and both recursive calls advance to i + 1, so no position is reused. Since every value is positive, a sum above target cannot recover, and a sum equal to target cannot be extended to another solution. Sorting each successful path makes two keys equal exactly when they describe the same value multiset. The set therefore stores every valid value combination exactly once.

Dry Run

Subset Filter + Dedup: variable states at each step
Entry from	i	path	total	Action (take before skip)
root	0	[]	0	take 10 at 0, then restore [] and skip
take index 0	1	[10]	10	overshoot; return
skip index 0	1	[]	0	take 1 at 1, then restore [] and skip
take index 1	2	[1]	1	take 2 at 2, then restore [1] and skip
take index 2	3	[1,2]	3	take 7 at 3, then restore [1,2] and skip
take index 3	4	[1,2,7]	10	overshoot; return
skip index 3	4	[1,2]	3	take 6 at 4, then restore [1,2] and skip
take index 4	5	[1,2,6]	9	overshoot; return
skip index 4	5	[1,2]	3	take 1 at 5, then restore [1,2] and skip
take index 5	6	[1,2,1]	4	take 5 at 6, then restore [1,2,1] and skip
take index 6	7	[1,2,1,5]	9	overshoot; return
skip index 6	7	[1,2,1]	4	exhausted; return
skip index 5	6	[1,2]	3	take 5 at 6, then restore [1,2] and skip
take index 6	7	[1,2,5]	8	record [1,2,5]; return
skip index 6	7	[1,2]	3	exhausted; return
skip index 2	3	[1]	1	take 7 at 3, then restore [1] and skip
take index 3	4	[1,7]	8	record [1,7]; return
skip index 3	4	[1]	1	take 6 at 4, then restore [1] and skip
take index 4	5	[1,6]	7	take 1 at 5, then restore [1,6] and skip
take index 5	6	[1,6,1]	8	record [1,1,6]; return
skip index 5	6	[1,6]	7	take 5 at 6, then restore [1,6] and skip
take index 6	7	[1,6,5]	12	overshoot; return
skip index 6	7	[1,6]	7	exhausted; return
skip index 4	5	[1]	1	take 1 at 5, then restore [1] and skip
take index 5	6	[1,1]	2	take 5 at 6, then restore [1,1] and skip
take index 6	7	[1,1,5]	7	exhausted; return
skip index 6	7	[1,1]	2	exhausted; return
skip index 5	6	[1]	1	take 5 at 6, then restore [1] and skip
take index 6	7	[1,5]	6	exhausted; return
skip index 6	7	[1]	1	exhausted; return
skip index 1	2	[]	0	take 2 at 2, then restore [] and skip
take index 2	3	[2]	2	take 7 at 3, then restore [2] and skip
take index 3	4	[2,7]	9	overshoot; return
skip index 3	4	[2]	2	take 6 at 4, then restore [2] and skip
take index 4	5	[2,6]	8	record [2,6]; return
skip index 4	5	[2]	2	take 1 at 5, then restore [2] and skip
take index 5	6	[2,1]	3	take 5 at 6, then restore [2,1] and skip
take index 6	7	[2,1,5]	8	duplicate key; return
skip index 6	7	[2,1]	3	exhausted; return
skip index 5	6	[2]	2	take 5 at 6, then restore [2] and skip
take index 6	7	[2,5]	7	exhausted; return
skip index 6	7	[2]	2	exhausted; return
skip index 2	3	[]	0	take 7 at 3, then restore [] and skip
take index 3	4	[7]	7	take 6 at 4, then restore [7] and skip
take index 4	5	[7,6]	13	overshoot; return
skip index 4	5	[7]	7	take 1 at 5, then restore [7] and skip
take index 5	6	[7,1]	8	duplicate key; return
skip index 5	6	[7]	7	take 5 at 6, then restore [7] and skip
take index 6	7	[7,5]	12	overshoot; return
skip index 6	7	[7]	7	exhausted; return
skip index 3	4	[]	0	take 6 at 4, then restore [] and skip
take index 4	5	[6]	6	take 1 at 5, then restore [6] and skip
take index 5	6	[6,1]	7	take 5 at 6, then restore [6,1] and skip
take index 6	7	[6,1,5]	12	overshoot; return
skip index 6	7	[6,1]	7	exhausted; return
skip index 5	6	[6]	6	take 5 at 6, then restore [6] and skip
take index 6	7	[6,5]	11	overshoot; return
skip index 6	7	[6]	6	exhausted; return
skip index 4	5	[]	0	take 1 at 5, then restore [] and skip
take index 5	6	[1]	1	take 5 at 6, then restore [1] and skip
take index 6	7	[1,5]	6	exhausted; return
skip index 6	7	[1]	1	exhausted; return
skip index 5	6	[]	0	take 5 at 6, then restore [] and skip
take index 6	7	[5]	5	exhausted; return
skip index 6	7	[]	0	exhausted; return
root complete	0	[]	0	return [[1,1,6],[1,2,5],[1,7],[2,6]] in any order

Complexity Analysis

Time Complexity

O(n \log(n+1) \cdot 2^n)

Space Complexity

O(n + L)

Let n be the number of positions, k = min(n, target), R the number of distinct returned combinations and L their total number of stored values. Include/skip explores at most O(2^n) calls. A successful path of at most k values is copied and sorted, costing O(k log(k+1)); hashing or stringifying its key also costs O(k) under the bounded value range. Hence O(2^n k log(k+1) + L) is a more detailed upper bound, with the displayed n-based bound as a coarse simplification. A mutable path and recursion stack take O(n). Only successful unique keys are retained, not all visited subsets: the key set and returned lists use O(L) storage; Python tuples and JavaScript strings coexist with output lists, while Java shares each immutable-by-convention key list with its result. Temporary duplicate keys and sorting workspace add O(k), covered by O(n). This pedagogical approach can still explore exponentially many positional choices and is unsuitable for hard length-100 inputs.

Code

Solution.java

1import java.util.ArrayList;2import java.util.Collections;3import java.util.HashSet;4import java.util.List;5import java.util.Set;6
7class Solution {8    public List<List<Integer>> combinationSum2(int[] candidates, int target) {9        List<List<Integer>> res = new ArrayList<>();10        Set<List<Integer>> seen = new HashSet<>();11        dfs(candidates, 0, 0, target, new ArrayList<>(), res, seen);12        return res;13    }14
15    private void dfs(int[] candidates, int i, int total, int target, List<Integer> path,16                     List<List<Integer>> res, Set<List<Integer>> seen) {17        // Positivity means a complete sum cannot be extended to another answer.18        if (total == target) {19            List<Integer> key = new ArrayList<>(path);20            // Equal value multisets share one key, regardless of chosen positions.21            Collections.sort(key);22            if (seen.add(key)) res.add(key);23            return;24        }25        if (i == candidates.length || total > target) return;26        path.add(candidates[i]);27        dfs(candidates, i + 1, total + candidates[i], target, path, res, seen);28        // Restore the prefix before the sibling skip branch.29        path.remove(path.size() - 1);30        dfs(candidates, i + 1, total, target, path, res, seen);31    }32}

Hints

Hint 1

Treat every position as a one-time resource; choosing one of two equal values must not prevent choosing the other later.

Hint 2

An include/skip search is complete, but duplicate values can produce the same answer through different positions. How could sorted successful paths serve as deduplication keys?

Hint 3

Sort once, advance to i + 1 after a pick, and skip a repeated value only when i > start at the current level. Positivity also lets a too-large sorted value terminate the loop.

Edge Cases

All equal values: [1,1,1] with target 2 returns [[1,1]], using two distinct positions rather than deleting all duplicates.
A single value can be an exact answer: [5] with target 5 returns [[5]]. A single 1 with target 2 returns [].
When every value exceeds the target, the sorted approach breaks immediately; [50,50] with target 30 returns [].
Multiple equal candidates need enough occurrences: [2,2] with target 6 has no answer, while [2,2,2] returns [[2,2,2]].
The target bound limits each successful path to at most 30 values because every candidate is positive; the include/skip call stack can still reach all 100 positions.

Common Mistakes and Interview Tips

Skipping every repeated value, including at a deeper level, deletes [1,1,6]. The condition is i > start, not i > 0.
Recursing from i instead of i + 1 permits unlimited reuse and answers Combination Sum rather than Combination Sum II.
Sorting JavaScript without a numeric comparator puts 10 before 2 and breaks the pruning rule.
Saving the mutable path directly makes earlier results change during backtracking; copy it at every successful leaf.
Claiming constant or linear total space while ignoring stored output and successful deduplication keys hides potentially large allocations.
Interview tip: state the difference between duplicate sibling choices and repeated values along one path, and explain that sorting mutates the input in these snippets.

Key Takeaway

Single-use searches with duplicates stay unique through one rule: sort first, then never start the same value twice at the same level.