Problem Description
Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target. Each number in candidates may only be used once in the combination. The solution set must not contain duplicate combinations.
Key Insights
- The problem requires finding combinations that sum to a specific target while ensuring no duplicates.
- Each number can be used only once, necessitating careful tracking of indices during the search.
- A backtracking approach is suitable for exploring all potential combinations and pruning those that exceed the target.
- Sorting the candidates helps in easily skipping duplicates.
Space and Time Complexity
Time Complexity: O(2^N) in the worst case, where N is the number of candidates, as each candidate can either be included or excluded from a combination.
Space Complexity: O(N) for the recursion stack in the worst case, plus O(K) for storing each combination, where K is the length of the combination.
Solution
We will use a backtracking algorithm to explore all possible combinations of the candidate numbers. We start by sorting the candidates to efficiently handle duplicates and then recursively build combinations. At each step, we either include the current candidate or skip it, ensuring we do not consider the same number in the same position again. Once we reach the target sum, we store the valid combination.