# Leetcode 40 Solution

https://leetcode.com/problems/combination-sum-ii

## Thinking Process

This is a question similar to the last one. The difference is that we can only use each element once.

For this question, we will define the same state as the last one, `(selected, s, i)`. `selected` means the candidates we selected. `s` is the sum of all the current selected candidates. `i` means `i`th candidate is the next candidate we are considering to select.

The difference here is that the transition of the graph.

Since we are not going to be able to solve the problem faster than `O(N lg N)`, let’s just sort it first.

The initial state is still `([], 0, 0)`. For each state, we first fine all the elements same to `candidates[i]`, let’s say they are `i -> j`.

• Not select the `i`th element, then the next state will be `(selected, s, j + 1)`.
• Select one `i`th element, then the next state will be `(selected, s + candidates[i] * 1, j + 1)`.
• Select two `i`th elements, then the next state will be `(selected, s + candidates[i] * 2, j + 1)`.
• Select (j - i + 1) `i`th elements, then the next state will be `(selected, s + candidates[i] * (j - i + 1), j + 1)`.

Note that no matter how many `candidates[i]` we select, the last element of the next state is always `j + 1`, because we won’t consider `candidates[i]` anymore.

Once we find a state which has `s == target`, we collect the results.

## Algorithm Animation

Test case: `candidates = [2,2,3,5], target = 5`

frame:

## Time & Space Complexity

Assuming `N` is the size of `candidates`,

• Time complexity: `O(2^N)`
• Space complexity: `O(N)`

## Solution

``````class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
ans = []

candidates.sort()

def get_combo(selected, s, i):
if s == target:
ans.append(list(selected))
return

if i == len(candidates):
return

j = i
while j < len(candidates) - 1 and candidates[j] == candidates[j + 1]:
j += 1

# Do not use candidates[i] at all.
get_combo(selected, s, j + 1)

# Use candidates[i] for (k + 1) times.
for k in range(j - i + 1):
if s + candidates[i] * (k + 1) > target:
k -= 1
break
selected.append(candidates[i])
get_combo(selected, s + candidates[i] * (k + 1), j + 1)

while k >= 0:
selected.pop()
k -= 1

get_combo([], 0, 0)

return ans
``````