Combination Sum Ii - Leetcode Solution

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:

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

Output:

[ [1,1,6], [1,2,5], [1,7], [2,6] ]

Solution:

This problem is a variation of the classic combination sum problem where we need to find all unique combinations of a set of numbers that add up to a given target. We can use the same approach as the combination sum problem to solve this problem as well. However, we need to add an additional check to ensure that no duplicate combinations are generated.

The approach we will take is a recursive backtracking approach. We will start with an empty array as the current combination, and we will add numbers to this combination one at a time. At each step, we will check if the current combination adds up to the target. If it does, we will add it to the list of valid combinations. If not, we will continue exploring all possible combinations that can be formed with the remaining numbers, taking care to avoid adding duplicate combinations.

Here are the steps to implement this algorithm:

1. Sort the input array in ascending order. This will ensure that duplicates are adjacent to each other.

2. Initialize an empty list to hold all valid combinations.

3. Define a recursive function called backtrack that takes as input the current combination, the remaining numbers to consider, and the target.

4. If the current combination adds up to the target, add it to the list of valid combinations. Otherwise, continue exploring all possible combinations that can be formed with the remaining numbers.

5. To avoid duplicate combinations, we will skip over any numbers that are the same as the previous number we added to the current combination. This is because any combination that includes the first occurrence of a duplicate will be the same as a combination that includes the second occurrence of the duplicate.

6. Call the backtrack function with an empty array as the current combination, the entire input array as the remaining numbers to consider, and the target as the target sum.

7. Return the list of valid combinations.

Here is the Python 3 code for the solution:

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        # Step 1: Sort the input array in ascending order
        candidates.sort()

        # Step 2: Initialize an empty list to hold all valid combinations
        result = []

        # Step 3: Define the recursive backtrack function
        def backtrack(curr_combination, remaining_nums, target_sum):
            # Base case: If the target sum is reached, add the current combination to the result list
            if target_sum == 0:
                result.append(curr_combination)
                return

            # Recursive case: Explore all possible combinations that can be formed with the remaining numbers
            for i in range(len(remaining_nums)):
                # Skip over duplicates to avoid generating duplicate combinations
                if i > 0 and remaining_nums[i] == remaining_nums[i-1]:
                    continue

                # If the current number is larger than the remaining target sum, skip it
                if remaining_nums[i] > target_sum:
                    break

                # Recursively get all combinations that can be formed with the remaining numbers
                backtrack(curr_combination + [remaining_nums[i]], remaining_nums[i+1:], target_sum - remaining_nums[i])

        # Step 4: Call the backtrack function with an empty array as the current combination, the entire input array as the remaining numbers to consider, and the target as the target sum
        backtrack([], candidates, target)

        # Step 7: Return the list of valid combinations
        return result

Time Complexity:

The time complexity of this algorithm is O(2^n), where n is the length of the input array. In the worst case, every number in the input array can be included or excluded from the combination. However, the actual time complexity will be lower than this because we skip over duplicates and numbers that are larger than the target sum.

Space Complexity:

The space complexity of this algorithm is O(n), where n is the length of the input array. This is the maximum amount of extra space that can be used to store the current combination at any point in the algorithm.

1