Combination Sum II

Backtracking

Problem

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.

For example:

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

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

Thought Process

"i > index and candidates[i] == candidates[i-1]" (which checks for duplicates) only pertains to the first section of for-loop numbers because for a repeated number i, we don't want to include the combinations with the other numbers again that we already accounted for with the first occurrence of that element. See above with repeated 1s.

• Since some elements can be repeated in the input array, we can handle the case of duplicate combinations occuring due to repeated elements by sorting the input list and in our for loop we will check if candidates[i] == candidates[i-1] and continue if this is true because since we already came across that same element previously we don't want to do it again

Solution

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        soln = []
        self.helper(sorted(candidates), target, 0, [], soln)
        return soln
    
    def helper(self, nums, target, index, sums, soln):
        
        if target == 0:
            soln.append(list(sums))
            return
        elif target < 0:
            return
        
        for i in range(index, len(nums)):
            if i > index and nums[i] == nums[i-1]:
                continue 
            sums.append(nums[i])
            self.helper(nums, target - nums[i], i+1, sums, soln)
            sums.pop()
        

Key Points

• Need to sort the input list in order to check for duplicates

• Same approach as Combination Sum I where are target dictates when we begin to backtrack

Time Complexity

• Time: $O(2^n)$ because we are generating all these combinations and have n numbers at every step and 2 choices (either take it or leave it) (see Time complexity for Subsets problem for a detailed explaination).

• Space: $O(n)$ because all our recursive calls will go as deep as how many candidates we have.