Problem statement

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

Solution 1

Quite similar to previous problem, backtracking. The difference here is that we need to sort numbers first and then when we iterate, skip some numbers, for example if we have [1, 1, 2, 2, 2, 2, 3, 3, 4, 4, 4] and we take second 2, then what we can take next is either next 2 or first 3 or first 4. Actually what we have here is Knapsack problem, where we need to find all solutions.

Complexity

Potential complexity is O(2^n), total number of solutions.

Code

class Solution:
    def combinationSum2(self, candidates, target):
        def dfs(target, curr_sol, k):
            if target == 0:
                self.sol.append(curr_sol)
                return

            if target < 0 or k >= n - 1:
                return

            next_list = [k+1] + [i for i in range(k+2, n) if cand[i] != cand[i - 1]]

            for i in next_list:
                dfs(target - cand[i], curr_sol + [cand[i]], i)

        self.sol = []
        cand = sorted(candidates)
        n = len(cand)
        dfs(target, [], -1)
        return self.sol

Solution 2

Actually, we can do a bit better and use dynamic programming here to save in table[k] all possible solutions with sum equal to k.

Complexity

Complexity is the same as previous approach.

Code

#### borrowed solution
class Solution:
    def combinationSum2(self, candidates, target):
        candidates.sort()
        table = [None] + [set() for i in range(target)]
        for i in candidates:
            if i > target:
                break
            for j in range(target - i, 0, -1):
                table[i + j] |= {el + (i,) for el in table[j]}
            table[i].add((i,))
        return map(list, table[target])