Find a lesson, question or project

Start typing to search published content and planned structures.

↑ ↓ moveEnter openEsc close

Combination Sum II in Java: Use Each Index Once, Skip Duplicate Branches

Understand i+1, sorted candidate pruning and sibling duplicate skipping with repeated values, a worked target-sum example and commented Java.

MediumRecursion and backtrackingPattern: recursion, backtracking

Problem statement

Return unique combinations adding up to target when each input position may be used only once. Candidate values may repeat. Using both 1s in [1,1,6] is legal; returning that value list twice is not.

The LeetCode contract permits 1–100 positive values from 1–50 and target 1–30. The supplied task asks for sorted answers; this implementation’s sorted choices generate lexicographic combinations as well. We sort a copy rather than mutate the caller’s input.

Constraints & requirements

CONTRACT
Verified bounds: 1–100 values, each 1–50, target 1–30. Sort a copy, skip equal sibling choices, and recurse from i+1. Repeated values within a valid combination are allowed.

Examples 3 test cases

  1. Example 1 Case 1

    Input
    nums=[10,1,2,7,6,1,5]; target=8
    Output
    [[1,1,6],[1,2,5],[1,7],[2,6]]

    Two different positions containing 1 can both be used.

  2. Example 2 Case 2

    Input
    nums=[2,5,2,1,2]; target=5
    Output
    [[1,2,2],[5]]

    Three copies of 2 must not duplicate the [1,2,2] answer.

  3. Example 3 Case 3

    Input
    nums=[2]; target=1
    Output
    []

    No input position closes the target gap.

Solve on LeetCode ↗

Hints Optional

Hints become more specific one step at a time.
01Hint 1

Sorting puts equivalent next choices side by side.

02Hint 2

Skip nums[i]==nums[i-1] only when i>start.

03Hint 3

Advance to i+1 so a selected position cannot be used again.

How to think before coding

Use start to mean the first index this call may select. After selecting i, recurse from i+1 so that position cannot be reused. Skip an equal value only when i>start: equal siblings duplicate answers, while an equal value at a deeper level may be required. Save a COPY only at remaining==0, and undo after each child.

Brute force and the improvement

Enumerate every index subset, calculate its sum, and put matching sorted value lists in a set. For N positions, checking/copying can take O(N·2^N) time; the working selection uses O(N), and the deduplication set may retain output-sized storage. This correctly allows two equal values from different positions, but repeatedly builds equivalent answers. Sort a copy first, skip equal SIBLING choices, and stop as soon as a positive candidate exceeds the remaining target. The search is still exponential in the worst case; pruning is not a polynomial guarantee.

Intuition: duplicates are about branches, not forbidden values

Sort [10,1,2,7,6,1,5] into [1,1,2,5,6,7,10]. At the root, choosing the first 1 and choosing the second 1 would begin equivalent value-list answers. Explore only the first such sibling choice.

But after choosing the first 1, the second 1 belongs to the next level. Allow it, or you lose [1,1,6].

That distinction is exactly i > start && nums[i] == nums[i-1]. Here start is where this call’s candidates begin; i is the current loop choice. When i equals start, it is the first sibling and must be allowed.

Algorithm

  1. Sort a copy of the candidates.
  2. Save a path copy when its remaining target is zero.
  3. Loop over candidate positions from start.
  4. Skip equal sibling choices, not equal values everywhere.
  5. Break when the sorted positive value exceeds the gap.
  6. Choose, recurse from i+1, then remove the choice.

Java solution

Sort a copy so the caller’s input stays unchanged. The same-level duplicate condition avoids repeated answers; positive sorted values allow the oversized-candidate break.

Java
import java.util.*;

class Solution {
    public static List<List<Integer>> combinationSum2(int[] nums, int target) {
        int[] sorted = nums.clone(); // Preserve the caller's array while preparing adjacent duplicates.
        Arrays.sort(sorted);
        List<List<Integer>> result = new ArrayList<>();
        chooseOnce(sorted, 0, target, new ArrayList<>(), result);
        return result;
    }
    private static void chooseOnce(int[] nums, int start, int remaining,
            List<Integer> path, List<List<Integer>> result) {
        if (remaining == 0) { // Only target-reaching paths are answers.
            result.add(new ArrayList<>(path)); // Save an independent snapshot.
            return;
        }
        for (int i = start; i < nums.length; i++) { // Try each possible NEXT index.
            if (i > start && nums[i] == nums[i - 1]) continue; // Skip equal SIBLING choices only.
            if (nums[i] > remaining) break; // Sorted positive values after this are too large as well.
            path.add(nums[i]);
            chooseOnce(nums, i + 1, remaining - nums[i], path, result); // Next index: no reuse.
            path.remove(path.size() - 1); // Restore the parent's prefix for its next candidate.
        }
    }

    public static void main(String[] args) {
        System.out.println(combinationSum2(new int[]{10, 1, 2, 7, 6, 1, 5}, 8)); // [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]
    }
}

The default invocation returns [[1,1,6],[1,2,5],[1,7],[2,6]]. Advancing to i+1, not start+1, means the next call starts after the position actually chosen.

Recursion tree and dry run

Numbered illustrated dry run for Combination Sum II; the text transcript explains the states.
Follow the numbered panels in order. Open full-size dry run ↗
Read the text transcript

Follow the Java, step by step

Example: nums = [10,1,2,7,6,1,5], target = 8

What to track: Track start, loop index i, remaining and path. The input is cloned and sorted to [1,1,2,5,6,7,10]. This follows the first answer and the root duplicate skip; other successful siblings are summarized.

  1. Prepare adjacent duplicates

    Java operationArrays.sort(sorted);
    Statesorted = [1,1,2,5,6,7,10]; start = 0; remaining = 8; path = []

    Sorting the cloned array makes equal sibling choices easy to recognize without modifying nums.

  2. Choose the first 1

    Java operationchooseOnce(nums, i + 1, remaining - nums[i], path, result);
    Statechild: start = 1; remaining = 7; path = [1]

    Advancing to i + 1 forbids reusing the chosen position, unlike Combination Sum I.

  3. Choose the second 1 deeper

    Java operationif (i > start && nums[i] == nums[i - 1]) continue;
    Stateat start = 1, i = 1: i > start is false; child start = 2, remaining = 6, path = [1,1]

    An equal value at the first choice of a deeper call is allowed. It is a different unused array position.

  4. Try a branch that fails

    Java operationif (nums[i] > remaining) break;
    Statechoosing 2 gives remaining = 4 and path = [1,1,2]; its first available value is 5 > 4

    The sorted suffix contains nothing small enough. This child returns; its caller removes 2. A later take-5 child similarly cannot fill remaining = 1.

  5. Choose 6 and save

    Java operationresult.add(new ArrayList<>(path));
    Stateremaining = 0; path = [1,1,6]; result = [[1,1,6]]

    The parent with remaining = 6 reaches candidate 6 after the failed smaller branches. The saved list is independent of path.

  6. Restore and keep enumerating

    Java operationpath.remove(path.size() - 1);
    Statepath becomes [1,1], then [1] when that call finishes; later siblings save [1,2,5] and [1,7]

    Success does not stop an enumeration problem. Every caller restores its prefix before its next loop iteration.

  7. Skip a duplicate root branch

    Java operationif (i > start && nums[i] == nums[i - 1]) continue;
    Stateroot: start = 0; i = 1; nums[1] == nums[0] == 1; path = []

    Starting another root branch with the second 1 would reproduce the same value combinations. This sibling is skipped.

  8. Complete the remaining distinct branch

    Java operationchooseOnce(nums, i + 1, remaining - nums[i], path, result);
    Stateroot chooses 2; its remaining = 6 continuation chooses 6 and saves [2,6]

    All later root branches are still checked. The final result contains four combinations, not just the first traced answer.

Final result: [[1,1,6],[1,2,5],[1,7],[2,6]]; the caller’s original array is unchanged.

Worked example · read from top to bottom
root: start 0, gap 8, []
├─ choose first 1 → start 1, gap 7, [1]
│  ├─ choose second 1 → start 2, gap 6, [1,1]
│  │  └─ later choose 6 → gap 0 → save [1,1,6]
│  ├─ choose 2 → gap 5 → choose 5 → save [1,2,5]
│  └─ later choose 7 → save [1,7]
├─ second 1 at root → skip equivalent sibling
└─ choose 2 → gap 6 → choose 6 → save [2,6]

This is a pruned excerpt: it omits unsuccessful paths. After each child, undo removes only that child’s chosen last value; the parent’s earlier choices remain.

Why it works

Increasing indices ensure no position is reused. Sorted positive values justify breaking after an oversized value. Among equal sibling values, the first occurrence leaves at least as many identical copies available for deeper choices as a later occurrence would, so skipping later siblings loses no distinct value combination. Copying at gap zero saves exactly target-sum combinations.

Complexity and alternative approaches

For N candidates, O(N·2^N) is a conservative search-plus-copy bound, with O(N log N) sorting preprocessing. Actual visited states are reduced by positive-target pruning and duplicate skipping. A more precise measure is O(N log N + V + S), with V explored loop/search work and S total saved values.

Auxiliary space is O(N) for the sorted copy, current path and call stack; output is separate. Do not call this constant space just because the original array is untouched.

Enumerating every index subset and deduplicating matching lists with a set is correct but creates avoidable work and storage. A counting DP does not directly return these unique combinations. Reusable-candidate Combination Sum is a different contract, not another implementation of this one.

Common mistakes

  • i > 0 instead of i > start blocks legitimate repeated values below the root.
  • i instead of i+1 in the recursive call reuses a position.
  • Breaking on a large value before sorting misses smaller later candidates.
  • Removing duplicate input values before searching loses combinations such as [1,1,6].

Practice next

Next lessonSubsets II

Back to Recursion and backtracking →