Medium

Combination Sum II

LAB

Return unique combinations that sum to target when each candidate can be used at most once. Sort each combination and the outer list.

EXAMPLES

Example 1

Input
{
  "candidates": [
    10,
    1,
    2,
    7,
    6,
    1,
    5
  ],
  "target": 8
}

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

FUNCTION SHAPE

candidates: intArraytarget: int→intMatrix

SOLUTION NOTE

We use the same idea as before. A few differences: we can only use each number at most once, so we need to backtrack on j+1 instead of j. We also need to sort. This will prevent duplicates like [1,1,6] vs [6,1,1]. (imagine A = [1,1,6,1,1]) The naive version is actually too slow. We also need to prevent duplicates like [1,1,6] vs [1,1,6]. (imagine A = [1,1,1,6]) So we effectively use a 'while' loop like in Two Pointers, to move over the duplicates.

Reveal reference solution +

pythonREFERENCE

def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
    res = []
    curr = []
    curr_target = target
    n = len(candidates)
    candidates.sort()  # need this to skip multiple same values in order...

    def backtrack(i):
        nonlocal curr_target
        if curr_target < 0: return
        if curr_target == 0:
            res.append(curr.copy())
        else:
            for j in range(i, n):
                if j >= i+1 and candidates[j] == candidates[j-1]: continue  # NEED THIS... skip dups
                curr.append(candidates[j])
                curr_target -= candidates[j]

                backtrack(j+1)

                curr_target += candidates[j]
                curr.pop()

    backtrack(0)
    return res

TimeO(n*2^n)

SpaceO(n*2^n)

Open on LeetCode ↗