#40 Combination Sum II

frequently reported atMeta Microsoft Amazon Google

the problem

In plain words

Candidates may contain duplicates; each index may be used at most once. Return all unique combinations that sum to target.

in candidates = [10,1,2,7,6,1,5], target = 8

out [[1,1,6],[1,2,5],[1,7],[2,6]]

in candidates = [2,5,2,1,2], target = 5

out [[1,2,2],[5]]

1 ≤ candidates.length ≤ 100
1 ≤ candidates[i] ≤ 50
1 ≤ target ≤ 30

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternBacktracking: combinations & partitions

It's Subsets II with a sum: sort, skip equal neighbours at the same depth, recurse with i + 1, and break once a value exceeds what's left.

solutions

From brute force to optimal

Explore every index in/out and let a LinkedHashSet throw away repeated lists.

Sort (so equal combinations are equal lists).
Pick c[i] → recurse(i + 1); skip → recurse(i + 1).
Add hits to the set.

timeO(n·2ⁿ)

Every in/out pattern may be explored (bounded by remain), and each hit is copied and hashed.

spaceO(n + output)

Recursion depth plus the set of results.

javajava.util.*

1class Solution {2    public List<List<Integer>> combinationSum2(int[] candidates, int target) {3        Arrays.sort(candidates);                  // so equal combinations become equal lists4        Set<List<Integer>> seen = new LinkedHashSet<>();5        dfs(candidates, 0, target, new ArrayList<>(), seen);6        return new ArrayList<>(seen);7    }8 9    private void dfs(int[] c, int i, int remain, List<Integer> path, Set<List<Integer>> seen) {10        if (remain == 0) {11            seen.add(new ArrayList<>(path));      // duplicates silently ignored by the set12            return;13        }14        if (i == c.length || remain < 0) return;15        path.add(c[i]);                           // pick c[i] (each index once → move to i+1)16        dfs(c, i + 1, remain - c[i], path, seen);17        path.remove(path.size() - 1);18        dfs(c, i + 1, remain, path, seen);        // skip c[i]19    }20}

Loop i from start; skip c[i] == c[i-1] when i > start; break when c[i] > remain; recurse with i + 1.

Sort.
remain == 0 → record.
Skip same value at this depth; break if too big.
Choose, recurse(i + 1), un-choose.

timeO(n·2ⁿ)

Worst case is still exponential, but no duplicate branch is ever entered and the break cuts large values.

spaceO(n)

Recursion depth and path (excluding output).

javajava.util.*

1class Solution {2    public List<List<Integer>> combinationSum2(int[] candidates, int target) {3        Arrays.sort(candidates);4        List<List<Integer>> result = new ArrayList<>();5        backtrack(candidates, 0, target, new ArrayList<>(), result);6        return result;7    }8 9    private void backtrack(int[] c, int start, int remain, List<Integer> path, List<List<Integer>> result) {10        if (remain == 0) {11            result.add(new ArrayList<>(path));12            return;13        }14        for (int i = start; i < c.length; i++) {15            if (i > start && c[i] == c[i - 1]) continue; // same value already tried at this depth16            if (c[i] > remain) break;                    // sorted → the rest are too big17            path.add(c[i]);18            backtrack(c, i + 1, remain - c[i], path, result); // i+1: each number used once19            path.remove(path.size() - 1);20        }21    }22}

in the room

How to say it in the interview

talk track

Compare with LC 39 explicitly: two changes — i + 1 instead of i, and the duplicate skip.

traps

Skipping duplicates with i > 0 instead of i > start, which loses [1,1,6].

what they ask next

Follow-ups

Only say whether any combination exists?

That's subset sum: a boolean[] dp of size target + 1 with dp[0] = true; for each candidate c, loop s from target down to c and set dp[s] |= dp[s − c]. O(n·target) time.

Combination Sum III (LC 216): k distinct numbers from 1..9?

Same backtracking over 1..9 with i + 1, plus a size limit of k. No duplicate skip is needed — the values are already distinct.

before you submit

Edge cases to test

No combination ([3], target 2) → [].
All ones, [1, 1, 1, 1, 1] with target 3 → [[1, 1, 1]], listed once.
A number can't be reused: [2] with target 4 → [].

practise next