Combination Sum II: Finding Unique Combinations with Duplicates

This challenge asks you to find all unique combinations of numbers from a given set that sum up to a specific target value. The twist is that the input set may contain duplicate numbers, and each number can only be used once in each combination. This problem is fundamental in understanding backtracking algorithms and handling duplicate elements efficiently.

Problem Description

Given a collection of candidate numbers (which may contain duplicates) and a target number, find all unique combinations where the candidate numbers sum to the target.

Key Requirements:

1. Unique Combinations: The output should not contain duplicate combinations. For example, if the input is [1, 1, 2] and the target is 3, [1, 2] should appear only once, not twice (once for each 1).
2. No Duplicate Numbers within a Combination: Each number from the input collection can be used at most once in any given combination.
3. Sum to Target: Each combination must sum exactly to the target number.

Expected Behavior:

The function should return a list of lists, where each inner list represents a unique combination of numbers that satisfies the conditions. The order of combinations in the output list does not matter, nor does the order of numbers within a combination.

Edge Cases to Consider:

• Empty input collection.
• Target number that cannot be reached by any combination.
• Input collection with only duplicate numbers.
• Target number is zero.

Examples

Example 1:

Input: candidates = [10, 1, 2, 7, 6, 1, 5], target = 8
Output: [[1, 7], [1, 2, 5], [2, 6], [1, 1, 6]]
Explanation:
The combinations that sum to 8 are:
- 1 + 7 = 8
- 1 + 2 + 5 = 8
- 2 + 6 = 8
- 1 + 1 + 6 = 8 (using the two distinct '1's)
Note that [1, 7] is considered the same as [7, 1], and the duplicate '1's are handled to produce a unique set of combinations.

Example 2:

Input: candidates = [2, 5, 2, 1, 2], target = 5
Output: [[1, 2, 2], [5]]
Explanation:
- 5 = 5
- 1 + 2 + 2 = 5
Note how duplicate numbers are used appropriately to form unique combinations.

Example 3:

Input: candidates = [1, 1, 1], target = 2
Output: [[1, 1]]
Explanation:
Only one unique combination of two '1's sums to 2.

Constraints

• 1 <= candidates.length <= 30
• 1 <= candidates[i] <= 50
• 1 <= target <= 30
• The input candidates array may contain duplicates.
• The solution should be efficient, ideally with a time complexity suitable for the given constraints.

Notes

• A common approach to solve this problem is using a recursive backtracking algorithm.
• Handling duplicates is a crucial part of this challenge. Consider how sorting the input array can help in identifying and skipping duplicate combinations.
• Think about the state that needs to be maintained during the recursive calls, such as the current combination being built, the remaining target sum, and the index from which to consider candidates.