Leetcode - Combination Sum II

Question

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.

Ideas

• This one was a bit tough given all the DP practice I had been doing (which I think Tunnel Vision’d me into a “take” / “leave” approach)
• Following the Backtracking playbook
• Decision space = candidates
• State
  • Current path, current sum, current position in candidates
  • Cannot move backwards
  • State is invalid / we want to prune when
    • Our sum is > target
    • We are out of bounds
    • We are strictly at target (this is our desired case)
    • This is the trick: we run into a duplicate value at the same recursion depth
• Decision
  • For j in candidates
    • if we found a duplicate value at the same recursion depth prune = skip over choice (leave), we don’t want this since this will lead to duplicate solutions even if the duplicate value came from a different index. This branch could result in both branches choosing the same next value
    • Otherwise add j to current path
    • Backtrack
    • Pop choice from current path
• Base case is explored in state
• Call backtracking and return res

Solution