Leetcode Daily Question 13/08/2024 - 40. Combination Sum II

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.

from typing import List
class Solution:
  def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
    result = []
    path = []
    candidates.sort()
    
    def dfs(start, target):
      if target == 0:
        result.append(path[:])
      if target < 0:
        return 
      for i in range(start, len(candidates)):
        if i > start and candidates[i] == candidates[i-1]:
          continue
        if candidates[i] > target:
          break
        path.append(candidates[i])
        dfs(i + 1, target - candidates[i])
        path.pop()
        
    dfs(0, target)
    return result

Explanation:

To solve this problem, we can use dfs to explore all paths. A useful adjustment to make is to sort the candidates so that we can traverse all the paths continuously without terminating early.

Let's consider the following example.

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

#sort the candidates
candidates = [1,1,2,5,6,7,10]

#DFS 
Start at index 0, target = 8, and an empty path
We add 1 to the path, then we call dfs again to check. 
Since 1 < 8, target now becomes 7 > 0, so we move on to the next index and add it to the path.
path = [1,1]. Target = 6 > 0, path = [1,1,2]. Target = 4, path = [1,1,2,5].
Now, target = 4 - 5 = -1 < 0, we cannot continue this path, so we pop the last added element, path = [1,1,2]
path = [1,1,2,7], target = -3 < 0, so path again returns to [1,1,2]
path = [1,1,2,10] target = -6 < 0, so path returns to [1,1,2]. 
Since we have explored all possible paths of this configuration we pop the last element and add the next element. 
path -> [1,1] -> [1,1,5]
Continue as befoe, [1,1,5,7] means target < 0 so path returns to [1,1,5].

#We can avoid extra calculations by:
# - skipping elements if they are already bigger than the target
# - skipping elements if they constitue duplicated start points.

Putting this into code, we have.

def dfs(start, target):
  if target == 0:
    result.append(path[:])
    return
  if target < 0:
    return
  for i in range(start, len(candidates)):
    if i > start and candidates[i-1] == candidates[i]: #This ensures we dont need to explore duplicated paths.
      continue
   	if candidates[i] > target: #no need to explore paths starting with elements larger than target.
      break
    path.append(candidates[i])
    dfs(i+1, target - candidates[i])
    path.pop()

We just need to declare the starting conditions and return result.

def combinationSum2(candidates, target):
  result = []
  path = []
  candidates.sort()
  #INSERT DFS FUNCTION...
  dfs(0, target)
  return result

The final solution can be found near the top of the page.