LC 40 - Combination Sum II

Question

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.

Each number in candidates may only be used once in the combination.

Note: The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8
Output: 
[[1,1,6],[1,2,5],[1,7],[2,6]]

Example 2:

Input: candidates = [2,5,2,1,2], target = 5
Output:
[[1,2,2],[5]]

Constraints:

• 1 <= candidates.length <= 100
• 1 <= candidates[i] <= 50
• 1 <= target <= 30

Links

Question here and solution here

Solution

concept

This question is very similar to 39. Combination Sum. The difference is that we can only only use the given elements once and there are duplicates in the given number, and we do not want duplicate answer in the final output.

1. the way we handle it is to first sort the input array, this will makes all the duplicates are grouped together
2. when we go down the inclusive path, we can proceed normally, i.e. we can have duplicates as long as the input has duplicates, so the idx will be idx + 1
   1. when we go down the exclusive path, we will move our idx such that we skip all the duplicates. We can imagine that all the duplicates has been processed in the inclusive step above, since the answer with 1-, 2-, … , N-copy of that element has already been considered.

code

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

        def dfs(idx):
            if sum(tmp) >= target or idx >= len(candidates):
                if sum(tmp) == target:
                    ans.append(tmp.copy())
                return

            tmp.append(candidates[idx])
            dfs(idx + 1)
            tmp.pop()

            while idx < len(candidates) - 1 and candidates[idx] == candidates[idx + 1]:
                idx += 1
            dfs(idx + 1)

        dfs(0)
        return ans
        
class NeetSolution:
	"""
	same as above but pass in the total as well to avoid re-calculation of the sum each time
	"""
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        candidates.sort()

        def dfs(i, cur, total):
            if total == target:
                res.append(cur.copy())
                return
            if total > target or i == len(candidates):
                return

            cur.append(candidates[i])
            dfs(i + 1, cur, total + candidates[i])
            cur.pop()


            while i + 1 < len(candidates) and candidates[i] == candidates[i+1]:
                i += 1
            dfs(i + 1, cur, total)

        dfs(0, [], 0)
        return res

Complexity

time: $O(n * 2^n)$
space: $O(n)$