Find Unique One-Use Combination Sums with Negative Values
Company: ByteDance
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
# Find Unique One-Use Combination Sums with Negative Values
You are given an integer array `candidates`, which may contain negative values and duplicates, and an integer `target`.
Choose a nonempty subset of input occurrences whose values sum to `target`. Each occurrence may be used at most once. Return every distinct value combination exactly once.
Implement:
```text
combinationSumOnce(candidates, target) -> integer[][]
```
Within each combination, values must be in nondecreasing order. Sort the outer list lexicographically. Two combinations are duplicates when their ordered value sequences are equal, even if they use different equal-valued input occurrences.
Because negative values are allowed, do not prune solely because a partial sum exceeds `target`.
## Constraints
- `1 <= candidates.length <= 20`
- `-10^9 <= candidates[i], target <= 10^9`
- Every subset sum fits in a signed 64-bit integer.
## Examples
### Example 1
```text
candidates = [10, 1, 2, 7, 6, 1, 5]
target = 8
output = [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]
```
Equal `1` values come from separate occurrences, while duplicate value sequences are returned only once.
### Example 2
```text
candidates = [-3, -1, 2, 4]
target = 1
output = [[-3, 4], [-1, 2]]
```
Both combinations use each chosen occurrence once and demonstrate the reported negative-value variant.
Quick Answer: Find every unique combination that reaches a target when each input occurrence may be used once and candidates may be negative. The prompt defines duplicate handling and deterministic ordering while ruling out positive-only pruning that would miss valid combinations.
Given an integer array candidates, which may contain negative values and duplicates, and an integer target, choose a nonempty subset of input occurrences whose values sum to target. Each occurrence may be used at most once. Return every distinct value combination exactly once. Values within each combination must be nondecreasing, and the outer list must be lexicographically sorted. Two combinations are duplicates when their ordered value sequences are equal, even if they use different equal-valued occurrences. Because negative values are allowed, a partial sum above target does not justify pruning.
Constraints
- 1 <= candidates.length <= 20
- -10^9 <= candidates[i], target <= 10^9
- Every subset sum fits in a signed 64-bit integer.
- The selected subset must be nonempty, and each input occurrence may be used at most once.
- Return distinct nondecreasing value sequences in lexicographic outer order.
Examples
Input: ([10, 1, 2, 7, 6, 1, 5], 8)
Expected Output: [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]
Explanation: The first source example contains four distinct value sequences despite duplicate input ones.
Input: ([-3, -1, 2, 4], 1)
Expected Output: [[-3, 4], [-1, 2]]
Explanation: The second source example exercises the reported negative-value variant.
Hints
- The empty subset is never returned, including when target is zero.
- Negative values mean a partial sum does not establish that later choices cannot reach the target.
- Duplicate identity and output ordering are based on value sequences, not occurrence indices.