Find Unique One-Use Combination Sums with Negative Values

Problem Statement

Given an array of integers candidates that may contain duplicate elements as well as negative numbers, and an integer target, return all unique combinations of candidates where the chosen numbers sum to target.

Each number in candidates may only be used once per combination (based on its original index). The solution set must not contain duplicate combinations.

To ensure deterministic output:

• Each combination should be sorted in non-decreasing order.
• The list of combinations should be sorted in lexicographical order.

Function Signature

def combinationSumWithNegatives(candidates: list[int], target: int) -> list[list[int]]:
    pass

Input and Output

• Input: A list of integers candidates and an integer target.
• Output: A list of lists of integers representing all unique combinations that sum to target.

Constraints

• 1 <= len(candidates) <= 20
• -50 <= candidates[i] <= 50
• -500 <= target <= 500

Examples

Example 1:

Input: candidates = [2, -1, 3, -1, 1], target = 2
Output: [[-1, -1, 1, 3], [-1, 3], [2]]
Explanation:
- (-1) + (-1) + 1 + 3 = 2
- (-1) + 3 = 2
- 2 = 2
Note that while '-1' appears twice in candidates, identical combinations like using the first vs. second '-1' with '3' are deduplicated.

Example 2:

Input: candidates = [-2, 0, 2], target = 0
Output: [[-2, 0, 2], [-2, 2], [0]]

Edge Cases

• No combination adds up to target, in which case the function should return an empty list [].
• The array contains zero (0), which can be included without changing the sum.
• Standard pruning (sum > target) does not work because subsequent negative numbers can reduce the running sum.