Combination Sum II

Patrick Leaton

Published: May 12, 2021, 7:44 p.m.

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.

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

The description was taken from https://leetcode.com/problems/combination-sum-ii/.

Problem Solution

#O(2^N) Time, O(N) Space

class Solution:

def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:

output = []

candidates.sort()

def backtrack(start:int, combo:int, remaining:int) -> None:

if remaining == 0:

output.append(list(combo))

return

if remaining < 0:

return

for i in range(start, len(candidates)):

if candidates[i] > remaining:

return

if i > start and candidates[i] == candidates[i-1]:

continue

combo.append(candidates[i])

backtrack(i+1, combo, remaining - candidates[i])

combo.pop()

backtrack(0, [], target)

return output

Problem Explanation

This solution is nearly the same as the first Combination Sum question, with only a couple of differences.

Mainly, we will be sorting the array to skip any duplicate values, but we will also not be reusing values like we were in the first question.

Let's start by initializing our output array.

output = []

Let's also sort the candidates' array to group any duplicates together.

candidates.sort()

Next, we will create our recursive, backtrack function.

The function will take an index to begin a traversal from and a combo list that contains a Depth First Search path's current combination, as well as a remaining value that indicates what needs to be added to this current combination for it to equal the target value.

def backtrack(start:int, combo:int, remaining:int) -> None:

Let's set a couple of base cases for this function.

First, if the remaining value equals zero, then that means that the candidates within the current combination sum to the target value. If that is the case, then we will append the combination to the output by taking a deep copy so that the list isn't overwritten later.

We will then return from the function.

if remaining == 0:

output.append(list(combo))

return

Also, if the remaining value is less than zero then that means we overshot the target and we should return from this DFS path here since it will not lead to any combination that we will be able to use.

if remaining < 0:

return

We will now start creating the backtracking logic.

Let's create a loop that will iterate from a given starting number to the last number in the array of candidates.

This is how we will split up the scope of each combination through recursion.

for i in range(start, len(candidates)):

Next, we will implement the optimization that we can gain by sorting the array of candidates.

If the number in our current iteration is greater than the remaining value, then we should return now because this current DFS path is bad and we will overshoot our target by adding any more values from the candidate array.

This step isn't required but helps tremendously to prune the recursion tree.

if candidates[i] > remaining:

return

During an iteration, to skip appending duplicate combinations to the output, we will check if the iteration's i value is greater than the index that was passed to the function and also if the current element has the same value as the previous one.

We want to make sure that the first part of that condition is checked because, for example, let's take an input of [1,2,2], where the target is five.

We will have a DFS path that will go from [1], recurse to [1,2], and when it recurses to what should be [1,2,2], it would skip the second two and return from the path and not arrive at that valid combination.

We are still wanting duplicate values within the combinations as long as we aren't reusing the same candidate, we just don't want duplicate combinations.

if i > start and candidates[i] == candidates[i-1]:

continue

Next, we will append the current candidate number from the current iteration to the current combo and recurse the function by incrementing the starting number to the current iterator plus one, since we can't reuse candidate values within a combo unlike the previous version of this question. We will also be passing the combo and subtracting the remaining value by the current candidate.

combo.append(candidates[i])

backtrack(i+1, combo, remaining - candidates[i])

Note: this function call and the previous conditional statement that skips duplicate values is the only difference between this solution and the previous version of this problem.

After we have shot our DFS yoyo down and it has returned back to us, we will pop the last candidate from our combo.

combo.pop()

The reason we do this is that we want to allow the function to circulate increasing numbers for each position from the pool of candidates until we have gathered each combination from each valid DFS path.

Now that we have our backtrack function built, we just need to make the initial call by passing zero as the starting number, an initial empty combination, and the target number as the remaining value.

backtrack(0, [], target)

Once we have our output that contains each valid combination, we will return it and we're done with this question.

return output

The time and space complexity of this version of the question is a lot simpler than the previous one because we can't reuse candidate values within a combination unlike we did previously, so it will be O(2^N) time and O(N) space.