Leetcode 40. Combination Sum II

Problem

Leetcode 40 - Combination Sum II

Example:

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

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

Approach

Similar to the question from Leetcode 39, we can use sort then DFS. While we iterate we need to check for duplicate on the first element.

Here is the Python code for the solution:

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

        def dfs(i, target, arr):
            if target == 0:
                res.append(arr)
                return
            if target < 0 or i == len(candidates):
                return
            
            dfs(i+1, target-candidates[i], arr+[candidates[i]])

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

            dfs(i+1, target, arr)

        dfs(0, target, [])
        return res    

Time Complexity and Space Complexity

Time Complexity: $O(2^n)$

Space Complexity: $O(n)$