Start learning free

LESSON 362 OF 569 · BACKTRACKING

Combination Sum II in Java: Backtracking Without Repeats

Practice O(n · 2n) Read the full explanation

Given an array of integers candidates, which may contain duplicates, and an integer target, return every distinct combination of candidates that adds up to target.

Each candidate may be used at most once in a combination, so a number that appears twice in candidates can appear up to twice in one combination. Two combinations are the same when they hold the same numbers the same number of times, whichever copies of a repeated number they use: in [1,1,7] with target = 8, the first 1 with the 7 and the second 1 with the 7 are one combination, [1,7], and it must appear only once.

Write the numbers of each combination in ascending order, and return the combinations in lexicographic order: compare two combinations number by number, and the first position where they differ decides which one comes first. This is the order in which the search described in the note below finds them. If no combination adds up to target, return an empty array.

 

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8
Output: [[1,1,6],[1,2,5],[1,7],[2,6]]
Explanation: Sorted, the candidates are [1,1,2,5,6,7,10]. [1,1,6] uses both 1s.
[1,7] can be made with either 1, but it is listed once. [1,2,5] comes before [1,7] because at the second number, 2 is smaller than 7.

Example 2:

Input: candidates = [2,5,2,1,2], target = 5
Output: [[1,2,2],[5]]
Explanation: There are three 2s; [1,2,2] uses two of them and appears once. 5 alone is 5.

Example 3:

Input: candidates = [2,3], target = 4
Output: []
Explanation: 2 + 3 = 5 is too much, and the 2 can't be used twice, so no combination adds up to 4.

 

Constraints:

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

Note:

The tutorial uses backtracking, as in Combination Sum. Sort candidates. A call gets start, the first index it may still use, remaining, what the combination still needs, and current, the combination built so far. When remaining is 0, it saves a copy of current. Otherwise a loop tries each index i from start on as the next number: it adds candidates[i], calls itself with i + 1 and remaining - candidates[i], and removes the number again. Because the candidates are sorted, the loop can stop at the first one that is bigger than remaining.

Two things change from Combination Sum. First, the deeper call starts at i + 1, not at i: there, a number could be chosen again and again; here, each candidate is used at most once. Second, as in Subsets II, the loop skips candidates[i] when i > start and it equals candidates[i - 1]. Inside one call, every turn of the loop picks a different next number, and a second copy of the same value would build exactly the same combinations again. A copy is still taken when it is the first one this call tries, at i = start: that is how [1,1,6] gets its second 1.

The search is exponential: with n candidates, there are at most 2n ways to pick some of them, and copying a combination takes up to n steps, so the time is O(n · 2n) in the worst case. The sorted order keeps it far smaller in practice: the calls only build distinct combinations whose sum is at most target. Besides the answer, the extra space is O(n): the combination being built and one call per number in it.

STEP 1 OF 13
    Ctrl + Enter to check

    JAVA · BACKTRACKING

    Combination Sum Ii in Java, explained

    Problem overview

    The method combinationSum2 receives an int[] named candidates, which may contain duplicates, and an int named target. It returns a List<List<Integer>> with every distinct combination of candidates that adds up to target. Each candidate can be used at most once, so a value that appears twice in the array can appear up to twice in a combination. Two combinations are the same when they hold the same numbers the same number of times: with [1,1,7] and a target of 8, using the first 1 or the second 1 gives the same combination [1, 7], which must be listed once.

    Each combination is written in ascending order and the list is in lexicographic order. For [10,1,2,7,6,1,5] and target 8, the sorted candidates are [1,1,2,5,6,7,10] and the answer is [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]. For [2,3] and target 4 the answer is []: the 2 can't be used twice, and 2 + 3 is 5.

    Approach: sorted backtracking with a duplicate skip

    This is the Subsets II search with a sum attached. Sort the candidates. A call receives start, the first index it may use, remaining, how much the combination still needs, and current, the combination so far. When remaining is 0, the numbers in current add up to the target, so a copy is saved. Otherwise a loop tries each index i from start as the next number: add candidates[i], recurse with i + 1 and remaining - candidates[i], then remove it.

    Two details separate this from the version where numbers can be reused:

    • The deeper call starts at i + 1, not at i. Passing i would let the same candidate be chosen again and again. With that mistake, [2,3] and target 4 returns [[2, 2]] instead of [].
    • Duplicate values need the skip. Inside one call, every turn of the loop picks a different next number, and a second copy of a value already tried at this position would rebuild the same combinations. So the loop skips candidates[i] when i > start and it equals candidates[i - 1]. At i == start the value is the first one this call tries, so it is taken even if it equals its left neighbour. That is how [1, 1, 6] gets its second 1.

    Sorting also allows a cut-off. Once candidates[i] is bigger than remaining, every later candidate is at least as big, so none fits, and the loop can break instead of continuing.

    The runs show why the skip matters. For [1,1,7] and target 8, the solution returns [[1, 7]]. A version with the same search but no skip returns [[1, 7], [1, 7]]. A version that skips with i > 0 instead of i > start loses [1, 1, 6] on the first example and returns [[1, 2, 5], [1, 7], [2, 6]].

    Step by step

    1. Sort candidates with Arrays.sort. Equal values become neighbours, the output gets its order, and the loop can stop at the first number that is too big.
    2. Create result as an ArrayList of lists.
    3. Start the search at index 0 with the whole target still needed and an empty combination. backtrack is assumed to exist until it is written.
    4. Return result.
    5. Declare backtrack, a void method with the array, start, remaining, current and result.
    6. Check remaining == 0. Nothing is left to make up, so current is a full combination.
    7. Save a copy and return. new ArrayList<>(current) is a snapshot, because current keeps changing. Every candidate is at least 1, so adding more would overshoot the target and returning is right.
    8. Loop over the indexes from start.
    9. Skip repeats with continue when i > start and the value equals the previous one.
    10. Break when candidates[i] > remaining.
    11. Choose candidates[i] by adding it to current.
    12. Recurse with i + 1 and the reduced remaining.
    13. Undo by removing the last element, at index current.size() - 1.

    The solution in Java

    class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> result = new ArrayList<>();
        backtrack(candidates, 0, target, new ArrayList<>(), result);
        return result;
    }

    void backtrack(int[] candidates, int start, int remaining, List<Integer> current, List<List<Integer>> result) {
        if (remaining == 0) {
            result.add(new ArrayList<>(current));
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            if (i > start && candidates[i] == candidates[i - 1]) {
                continue;
            }
            if (candidates[i] > remaining) {
                break;
            }
            current.add(candidates[i]);
            backtrack(candidates, i + 1, remaining - candidates[i], current, result);
            current.remove(current.size() - 1);
        }
    }
}

    Java details worth noting: current.remove(current.size() - 1) passes an int, so it removes the element at that index. Passing an Integer would remove the first element equal to that value, which is a different operation. Also, new ArrayList<>(current) copies the elements; storing current itself would make every saved combination change as the search continues, and they would all end up empty.

    The order of the two checks matters. The skip comes first and the cut-off second; either order gives the same result here, but the skip must compare i with start, not with 0.

    Complexity

    With n candidates there are at most 2^n ways to pick some of them, and copying a combination takes up to n steps, so the worst case is O(n · 2^n) time. In practice it is far smaller: the sort lets the loop break early, and the duplicate skip means that only distinct combinations whose sum stays within the target are ever built. For example, 100 candidates equal to 1 with target 30 return a single combination of thirty 1s. Besides the answer, the extra space is O(n): the combination being built plus one call per number in it.

    Edge cases and common mistakes

    • No combination. Return an empty list, as in [2,3] with target 4.
    • Several copies of a value. [1,1,1,1] with target 3 returns [[1, 1, 1]], one combination, not four.
    • A single candidate equal to the target. [2,5,2,1,2] with target 5 contains [5] alone, next to [1, 2, 2].
    • Skipping with i > 0. It drops combinations that use two equal numbers.
    • Recursing with i. It reuses a candidate, which this problem forbids.
    • Forgetting to sort. The skip and the cut-off both rely on sorted order.

    Testing

    These inputs were run against the solution above:

    candidates, targetResult
    [10,1,2,7,6,1,5], 8[[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]
    [2,5,2,1,2], 5[[1, 2, 2], [5]]
    [2,3], 4[]
    [1,1,7], 8[[1, 7]]
    [1,1,1,1], 3[[1, 1, 1]]
    Keep going with Java500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free