Return every unique target-sum combination when duplicate candidate values exist and each index may be used once. Try it free and read the solution.

Combination Sum II – Solve Online

Decode String

3Sum Closest

Return every unique target-sum combination when duplicate candidate values exist and each index may be used once.

Given an integer array `candidates` that may contain duplicate values and a non-negative integer `target`, return every unique **non-empty** combination of numbers whose sum is exactly `target`. Each element of `candidates` may be used at most once per combination, so choosing a value consumes one specific array index.

For this question, the output order is part of the contract: first sort `candidates` in ascending order. Then each combination **must** list its values in the order they were chosen during a left-to-right index scan of that sorted array. The outer answer list **must** follow the exact depth-first search discovery order produced by standard backtracking that, at each recursion level, tries candidate indices in increasing order starting from the current position and **skips an index if it has the same value as the previous index already tried at that same recursion depth**. That duplicate-skip-at-the-same-level rule is required to avoid repeated combinations, and the DFS discovery order it creates is the required canonical output order.

**Input / output**
- Input: `candidates: int[]`, `target: int`
- Output: `int[][]` in the canonical DFS order described above

## Example
```json
Input: {"candidates":[10,1,2,7,6,1,5],"target":8}
Output: [[1,1,6],[1,2,5],[1,7],[2,6]]
```

## More examples
1. `candidates = [2,5,2,1,2], target = 5` returns `[[1,2,2],[5]]`.
2. `candidates = [3,4,9], target = 2` returns `[]`.
3. `candidates = [1,2,3], target = 0` returns `[]` because this bank expects only non-empty combinations and all candidate values are positive.

## Constraints
- `1 <= candidates.length <= 100`
- `1 <= candidates[i] <= 50`
- `0 <= target <= 30`

## Follow-up
Once the array is sorted, how can you prune the backtracking loop early when the next candidate is already larger than the remaining target?

- This is backtracking over indices, not over unlimited value reuse: once you take `candidates[i]`, the next recursive call must continue from `i + 1`.
- Duplicate values in the input are the real twist. If two equal numbers sit next to each other in the sorted array, starting a branch from both of them at the same recursion depth would create duplicate combinations.
- Sorting first gives you both pieces you need: deterministic canonical order and an easy adjacent-value check for duplicate skipping.

Recognize the once-only search space

- Sort the array, keep a `path`, and let each call choose the next index from `start` onward.
- When `remaining == 0`, record the current path immediately; that DFS discovery order is the required outer-list order.
- At a given recursion depth, skip `candidates[i]` when `i > start` and it matches `candidates[i - 1]`. That preserves one representative branch per equal-value run at that level.
- This baseline is fully correct, but it may still recurse into branches that already overshoot the target.

Baseline backtracking with same-level duplicate skipping

- After sorting, once `candidates[i]` is already larger than the remaining target, every later value is also too large.
- That means the current loop can `break` immediately instead of recursing into guaranteed failures.
- This optimization preserves the exact same canonical output order because it only removes branches that could never produce a valid combination.

Add sorted-array pruning

The algorithm sorts once, then backtracks left-to-right while skipping equal values at the same depth and breaking when the next candidate is too large. In the worst case it explores subset-style branches, so the time complexity is `O(n * 2^n)` and the extra recursion/path space is `O(n)` (excluding the returned output).

Final optimized solution and complexity

- Reusing the same index by recursing with `i` instead of `i + 1`, which accidentally turns the problem back into Combination Sum I.
- Skipping every duplicate globally instead of only duplicates at the same recursion depth. You still need to allow `[1,1,6]` when two separate `1` entries exist.
- Sorting after backtracking or post-sorting the output, which can hide ordering bugs instead of producing the required canonical DFS order directly.