Combination Sum II

1. The obvious way

   Generate all subsets, keep those that sum to target, de-duplicate with a set.

2. The key insight

   Sort. Recurse with (start, remaining). In the loop: skip a number if it equals the previous number AND it is not the first of this loop (this level already tried that value). Stop if the number is bigger than remaining. Choose it, recurse from the NEXT position (single use), un-choose.

3. The algorithm
   1. Sort the numbers.
   2. remaining == 0: save a copy.
   3. In the loop skip repeats of a value already tried at this level; stop when too big.
   4. Choose, recurse from the next position, un-choose.

Watch it run

found: [1,1,6]

def combination_sum2(candidates, target):
    candidates.sort()
    result = []
    chosen = []

    def pay(start, remaining):
        if remaining == 0:
            result.append(list(chosen))
            return
        for position in range(start, len(candidates)):
            if position > start and candidates[position] == candidates[position - 1]:
                continue                                # this level already tried this value
            note = candidates[position]
            if note > remaining:
                break
            chosen.append(note)
            pay(position + 1, remaining - note)         # each note is handed over only once
            chosen.pop()

    pay(0, target)
    return result

Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.