Leetcode 40 Solution

Leetcode Question Link

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 ith 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 ith element, then the next state will be (selected, s, j + 1).
• Select one ith element, then the next state will be (selected, s + candidates[i] * 1, j + 1).
• Select two ith elements, then the next state will be (selected, s + candidates[i] * 2, j + 1).
• …
• Select (j - i + 1) ith 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

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