{x}
blog image

Combination Sum II

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.

Note: The solution set must not contain duplicate combinations.

 

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8
Output: 
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

Example 2:

Input: candidates = [2,5,2,1,2], target = 5
Output: 
[
[1,2,2],
[5]
]

 

Constraints:

  • 1 <= candidates.length <= 100
  • 1 <= candidates[i] <= 50
  • 1 <= target <= 30

Solution Explanation for Combination Sum II

This problem asks to find all unique combinations of numbers from a given array (candidates) that sum up to a target value. Each number in candidates can be used only once. The key to solving this efficiently is to use backtracking with pruning to avoid redundant computations and duplicate combinations.

Approach: Backtracking with Pruning and Sorting

  1. Sorting: Sort the candidates array. This allows for easy pruning (explained below) by identifying and skipping duplicate numbers.

  2. Backtracking: A recursive function (dfs in the code examples) implements backtracking. The function explores all possible combinations by:

    • Base Case: If the current sum equals the target, a valid combination is found, and it's added to the result.
    • Recursive Step: The function recursively calls itself with:
      • The next number in candidates (including the current number in the combination).
      • Excluding the current number from the combination.

  3. Pruning: The crucial optimization is pruning. Because the array is sorted:

    • If the current sum exceeds the target, there's no need to continue exploring combinations with larger numbers. The function returns early.
    • If we encounter a duplicate number in consecutive positions, we skip it in the recursive call. This prevents generating duplicate combinations.

Time and Space Complexity Analysis

  • Time Complexity: In the worst case, the algorithm explores all possible subsets of the input array. The number of subsets is O(2n), where n is the length of candidates. For each subset, we need to check the sum, which takes O(n) time in the worst case. Therefore, the overall time complexity is O(n * 2n). However, the pruning significantly improves the performance in practice. The actual time taken is much less than the worst-case complexity in most instances.

  • Space Complexity: The space complexity is dominated by the recursion depth and the storage of the result. The maximum recursion depth is O(n) because at most, we can have a combination of all n numbers. The result set can store at most O(2n) combinations in the worst case. Hence, the overall space complexity is O(n + 2n) which simplifies to O(2n) because the exponential term dominates. Again, pruning reduces the space usage in practice.

Code Examples (Python, Java, C++, Go, TypeScript, Rust, JavaScript, C#)

The provided code examples in various languages demonstrate the algorithm. They all follow the same structure:

  1. Sort candidates.
  2. Implement the recursive dfs function for backtracking with pruning.
  3. Call dfs to start the search.

The core logic within the dfs function is consistent across all implementations, adapting only to the syntax differences of each programming language. Refer to the code section in the original response for detailed implementations in each of the mentioned languages.