Topics › Recursion and Backtracking › Subsequences Pattern

Combination Sum II

Medium TUF ID 865 A2ZSDE

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given an array candidates of positive integers, possibly containing duplicates, and a positive integer target. Return every unique combination of candidates whose values add up to target. Each index may be used at most once; two equal values at different indices are two separate elements, but two combinations that contain the same values the same number of times are the same combination and must be reported only once. Any order is fine.

Constraints: 1 ≤ n ≤ 100, 1 ≤ candidates[i] ≤ 50, 1 ≤ target ≤ 30.

Example 1

candidates = [10, 1, 2, 7, 6, 1, 5], target = 8
answer = [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]
// [1, 7] uses either of the two 1s, but it is listed once

Example 2

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

Example 3

candidates = [2, 2, 2], target = 7
answer = []           // an index cannot be reused, so 6 is the most we can reach

Approach 1: Brute force, generate everything and de-duplicate with a set

Intuition. Ignore uniqueness at first: the ordinary pick / not-pick recursion over the sorted array produces every index subset whose values sum to target. Because the array is sorted and elements are appended in index order, two index subsets with the same multiset of values produce identical lists, so a Set<List<Integer>> collapses them. The work is wasted in two ways: the duplicates are generated and hashed before being thrown away, and with many equal values the number of duplicate index subsets explodes ([1, 1, 1, 1] with target 2 builds [1, 1] six times).

Algorithm.

1. Sort a copy of the candidates.
2. bruteRec(i, target, cur): at i == n, insert a copy of cur into the set if target == 0.
3. If c[i] <= target: append c[i], recurse with (i + 1, target - c[i]), remove it.
4. Recurse with (i + 1, target).
5. Return the set’s contents as a list.

static List<List<Integer>> bruteForce(int[] candidates, int target) {
    int[] c = candidates.clone();
    Arrays.sort(c);
    Set<List<Integer>> seen = new LinkedHashSet<>();
    bruteRec(c, 0, target, new ArrayList<>(), seen);
    return new ArrayList<>(seen);
}

static void bruteRec(int[] c, int i, int target, List<Integer> cur, Set<List<Integer>> seen) {
    if (i == c.length) {
        if (target == 0) seen.add(new ArrayList<>(cur));
        return;
    }
    if (c[i] <= target) {                          // pick index i, then move on: an index is used at most once
        cur.add(c[i]);
        bruteRec(c, i + 1, target - c[i], cur, seen);
        cur.remove(cur.size() - 1);
    }
    bruteRec(c, i + 1, target, cur, seen);         // skip index i
}

Complexity. Time O(2^n · k) where k is the combination length: every index subset that stays within the target is visited, and each hit is copied and hashed. Space O(2^n · k) in the worst case for the set, plus O(n) stack.

Sorting is essential even here: without it [1, 7] and [7, 1] could both be produced from different index pairs and the set would not see them as equal.

Approach 2: Optimal, sorted loop that skips equal values at the same level

Intuition. Think of the recursion as choosing the next value to append. At a given level, once we have fully explored “append a 1 here”, trying “append the other 1 here” can only reproduce combinations we already have, because everything after the appended 1 is drawn from the same sorted remainder. So the rule is: at one level, each distinct value is tried once. Sorting puts equal values side by side, and the test j > start && c[j] == c[j - 1] detects “same value as the previous candidate at this level”. Note the j > start part: equal to the previous element is only a duplicate if that previous element was a sibling choice at this level, not the element chosen by the parent.

Because candidates are positive and sorted, the first candidate that exceeds the remaining target ends the loop, and reaching target == 0 is the success condition.

Algorithm.

1. Sort a copy of the candidates.
2. loopRec(start, target, cur): if target == 0, record cur and return.
3. For j = start .. n - 1: skip if j > start and c[j] == c[j - 1]; break if c[j] > target.
4. Append c[j], recurse with (j + 1, target - c[j]), remove it.

static List<List<Integer>> optimal(int[] candidates, int target) {
    int[] c = candidates.clone();
    Arrays.sort(c);
    List<List<Integer>> out = new ArrayList<>();
    loopRec(c, 0, target, new ArrayList<>(), out);
    return out;
}

static void loopRec(int[] c, int start, int target, List<Integer> cur, List<List<Integer>> out) {
    if (target == 0) {
        out.add(new ArrayList<>(cur));
        return;
    }
    for (int j = start; j < c.length; j++) {
        if (j > start && c[j] == c[j - 1]) continue;  // this value was already tried at this level
        if (c[j] > target) break;                      // sorted: later values are larger still
        cur.add(c[j]);
        loopRec(c, j + 1, target - c[j], cur, out);    // j + 1: each index is used at most once
        cur.remove(cur.size() - 1);
    }
}

Dry run on sorted c = [1, 1, 2, 5, 6, 7, 10], target = 8:

Result: [1, 1, 6], [1, 2, 5], [1, 7], [2, 6], each produced exactly once and no set needed.

Complexity. Time O(2^n · k) as a worst-case bound (an input with all-distinct values and a huge target is a full power set), but the skip rule removes every duplicate branch and the break removes every oversized one, so in practice the tree contains only useful nodes. Sorting is O(n log n). Space O(n) for the recursion and the working list.

Approach 3: Pick / not-pick where “not pick” skips the whole run of equal values

Intuition. The same uniqueness rule can be expressed in the two-branch style. When we pick c[i], continue normally at i + 1. When we do not pick c[i], we must also refuse every later copy of the same value: choosing “skip this 1, take the next 1” would produce exactly the combination that “take this 1” already produced. So the not-pick branch jumps to the first index holding a different value. Sorting again guarantees the copies are adjacent.

This form keeps the familiar shape of the subsequence recursion and makes the dedup rule a single while loop, which some people find easier to reason about than the j > start test.

Algorithm.

1. Sort a copy of the candidates.
2. skipRec(i, target, cur): if target == 0, record; if i == n or c[i] > target, return.
3. Pick: append c[i], recurse with (i + 1, target - c[i]), remove it.
4. Not pick: advance next past every element equal to c[i] and recurse with (next, target).

static List<List<Integer>> pickNotPickSkip(int[] candidates, int target) {
    int[] c = candidates.clone();
    Arrays.sort(c);
    List<List<Integer>> out = new ArrayList<>();
    skipRec(c, 0, target, new ArrayList<>(), out);
    return out;
}

static void skipRec(int[] c, int i, int target, List<Integer> cur, List<List<Integer>> out) {
    if (target == 0) {
        out.add(new ArrayList<>(cur));
        return;
    }
    if (i == c.length || c[i] > target) return;     // sorted: nothing from here on can fit
    cur.add(c[i]);                                  // pick c[i]
    skipRec(c, i + 1, target - c[i], cur, out);
    cur.remove(cur.size() - 1);
    int next = i + 1;                               // not pick: also skip every later element equal to c[i]
    while (next < c.length && c[next] == c[i]) next++;
    skipRec(c, next, target, cur, out);
}

Complexity. Identical to Approach 2: the two methods visit the same set of distinct combinations, just organised as a binary tree instead of a loop. Time O(2^n · k) worst case, space O(n).

Edge cases and pitfalls

• Wrong skip condition. if (c[j] == c[j - 1]) continue without j > start skips a legitimate second copy chosen one level deeper, and [1, 1, 6] disappears. The duplicate test must compare against the previous sibling, never against the parent’s choice.
• Not sorting. Both the set-based and the skip-based methods rely on equal values being adjacent and on combinations being built in non-decreasing order.
• Reusing an index. Passing j instead of j + 1 (or i instead of i + 1) turns the problem into Combination Sum and lets [2, 2, 2, 2] appear for [2, 2, 2], target 8.
• Storing the working list. out.add(cur) keeps a reference that backtracking will mutate; always copy.
• Many equal values. [1, 1, 1, 1] with target 2 has six index pairs but one combination. The tests check both the contents and the size of the result for the dedup methods, so an accidental duplicate fails even though the fingerprint would match after de-duplication.
• No answer. [3, 4] with target 2 returns an empty list. The success check sits at target == 0, and the loop never runs because 3 > 2.

Related problems

• Combination Sum allows unlimited reuse and has no duplicates; the only change is j versus j + 1 and no skip rule.
• Combination Sum III constrains the candidates to 1..9 and the size to k.
• Subsets II applies exactly the same duplicate-skipping rule to enumerate unique subsets without a target.
• Power Set is the unconstrained pick / not-pick enumeration this builds on.
• Check if there exists a subsequence with sum K is the yes/no version with a single-use rule and no output list.