Pick Each Number At Most Once to Reach a Target Sum

Medium20–25 min

Topics

BacktrackingRecursionArray

Companies

AmazonMicrosoftUber

You're given an array of positive integers, candidates, which may hold repeated values, and a target. Find every distinct combination of values that sums exactly to target — this time each position in the array can be used at most once, and even though positions repeat values, the result must not contain the same value-combination twice. Since each position is used 0 or 1 times, every combination is really a subset — brute force can enumerate all 2ⁿ of them and filter by sum, but has to actively watch for and discard duplicates that arise from picking different positions that happen to share a value. Sorting first turns that after-the-fact cleanup into a cheap, built-in check: equal values end up adjacent, so a single neighbor comparison at each step is enough to skip a duplicate before it's ever explored.

Test Case 1:

Input:candidates = [4, 4, 2, 1, 3], target = 7

Output:[[3, 4], [1, 2, 4]]

Explanation:There are two 4s available, but each position can only be picked once — [3, 4] uses one of them, and [1, 2, 4] uses the other; there's no third distinct multiset that sums to 7.

Test Case 2:

Input:candidates = [5, 5, 5], target = 10

Output:[[5, 5]]

Explanation:Three positions hold the value 5, so several different pairs of positions could be picked — but they all produce the identical multiset [5, 5], so it appears only once.

Test Case 3:

Input:candidates = [9, 9], target = 3

Output:[]

Explanation:Both available values already exceed the target, so no selection — not even a single one — can work.

Constraints

◆1 ≤ candidates.length ≤ 15
◆1 ≤ candidates[i] ≤ 25, and values may repeat within candidates
◆1 ≤ target ≤ 35
◆Each position in candidates may be used at most once per combination

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Enumerate Every Selection, Deduplicate by Value

Brute

Since every position is either picked or not, this is a subset problem: try all 2ⁿ position-selections via bitmask, sum each one, and keep the ones that hit target. Repeated values create the real cost here — two different position-selections that happen to carry the same values (e.g. picking the first 4 versus picking the second 4) produce the identical combination, so each match's values are sorted into a canonical key and checked against everything already recorded before being kept. Correct, but the full 2ⁿ selections are built and checked regardless of how many of them turn out to be redundant.

TimeO(2ⁿ · n log n)

SpaceO(2ⁿ · n)

Java

Try it out

class Solution {
    public int[][] combinationsUsingEachOnce(int[] candidates, int target) {
        int n = candidates.length;
        Set<String> seen = new HashSet<>();
        List<int[]> result = new ArrayList<>();
        for (int mask = 0; mask < (1 << n); mask++) {
            List<Integer> subset = new ArrayList<>();
            int sum = 0;
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    subset.add(candidates[i]);
                    sum += candidates[i];
                }
            }
            if (sum == target) {
                Collections.sort(subset);
                String key = subset.toString();
                if (seen.add(key)) {
                    int[] row = new int[subset.size()];
                    for (int j = 0; j < row.length; j++) row[j] = subset.get(j);
                    result.add(row);
                }
            }
        }
        return result.toArray(new int[0][]);
    }
}

Optimal — Sorted Backtracking, Skip Same-Level Duplicates

Optimal

Sort first, then build combinations one position at a time with two cooperating cuts. The prune cut is the same one as the unrestricted version: once a candidate would push the running sum past target, every candidate after it (sorted ascending) would too, so break immediately. The new cut handles duplicate values directly: within one call's loop, skip any candidate equal to the one tried just before it at that same position — trying it would only rebuild a combination already produced by the identical value picked a moment ago, never something new. No hashing or after-the-fact comparison is needed; duplicates are recognized and skipped the instant they'd be considered.

TimeO(2ⁿ)

SpaceO(n)