Combination Sum II medium

Problem Statement

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]] Explanation: 1 + 1 + 6 = 8 1 + 2 + 5 = 8 1 + 7 = 8 2 + 6 = 8

Example 2:

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

Steps

1. Sort the candidates: Sorting allows us to efficiently skip duplicate numbers and avoid generating duplicate combinations.
2. Backtracking: Use a recursive backtracking function to explore all possible combinations.
3. Recursive function: The function takes the current index, current combination, and remaining target sum as input.
4. Base cases:
   • If the remaining target sum is 0, a valid combination is found. Add it to the result list.
   • If the remaining target sum is negative or the index is out of bounds, backtrack.
5. Recursive steps:
   • Include the current element: Recursively call the function with the same index (to allow duplicates), adding the current element to the combination and subtracting its value from the target. Crucially, we increment the index to avoid reusing the same number again.
   • Exclude the current element: Recursively call the function with the incremented index (skipping the current element) without changing the combination or target.
6. Skip duplicates: After including an element, skip over subsequent occurrences of the same element to avoid generating duplicate combinations.

Explanation

The solution employs backtracking, a depth-first search technique to explore all possible combinations. Sorting the candidates is crucial for efficiently handling duplicates. By skipping over duplicates after including an element in the combination, we ensure that only unique combinations are generated. The base cases handle the scenarios where a valid combination is found or when further exploration is unnecessary.

Code

def combinationSum2(candidates, target):
    result = []
    candidates.sort()  # Sort to handle duplicates efficiently
    
    def backtrack(index, combination, remaining):
        if remaining == 0:
            result.append(combination.copy())
            return
        
        if remaining < 0 or index >= len(candidates):
            return

        # Include the current element
        combination.append(candidates[index])
        backtrack(index + 1, combination, remaining - candidates[index])  # Increment index to avoid reusing the same number
        combination.pop()

        # Exclude the current element
        # Skip duplicates: advance index until a different element is found
        i = index + 1
        while i < len(candidates) and candidates[i] == candidates[index]:
            i += 1
        backtrack(i, combination, remaining)


    backtrack(0, [], target)
    return result

Complexity

• Time Complexity: O(2^N * K), where N is the number of candidates and K is the average length of a combination. In the worst-case scenario, we explore all possible subsets.
• Space Complexity: O(N * K) due to the recursive call stack and the space used to store combinations. In the worst case, the call stack can reach a depth of N and each combination can have a length of K.