Problem of The Day: Combination Sum II

Problem Statement

Brute Force - TLE

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

        def dfs(i, curr_sum, curr):
            if curr_sum == 0:
                if curr not in res:
                    res.append(curr)
                return
            if curr_sum < 0 or i >= N:
                return

            dfs(i + 1, curr_sum - candidates[i], curr + [candidates[i]])
            dfs(i + 1, curr_sum, curr)


        dfs(0, target, [])
        return res

Intuition

My initial thoughts were focused on finding a way to generate all possible combinations of numbers from the given list that sum up to the target value. To ensure the combinations are unique and cover all possibilities, I knew I would need to employ a strategy that involved recursive exploration of the number list while avoiding duplicate combinations.

Approach

1. Sorting: First, I sorted the list of candidates. Sorting helps in easily skipping duplicates and ensures that the combinations are generated in a non-decreasing order, which is useful for avoiding duplicate results.

2. Recursive Function (DFS): I used a Depth-First Search (DFS) approach with a helper function dfs. This function explores each candidate and tries to build a combination that sums up to the target.

3. Avoiding Duplicates: While iterating through the candidates, I made sure to skip over duplicate numbers by checking if the current number is the same as the previous one (when j > i). This ensures that we only consider each unique combination once.

4. Base Cases: The recursive function handles two main base cases:

   • If curr_sum becomes 0, it means the current combination is valid and should be added to the result.
   • If curr_sum becomes negative or if we’ve exhausted all candidates (i >= N), the recursion should stop.

5. Recursive Exploration: For each candidate, the function recursively explores further possibilities by including the current candidate and moving to the next candidate.

Complexity

• Time Complexity: The time complexity is generally difficult to determine precisely due to the exponential nature of combination generation. In the worst case, it can be exponential in the number of candidates, approximately (O(2^N)), where (N) is the number of candidates. This is due to the need to explore all possible subsets.

• Space Complexity: The space complexity is (O(N)) in terms of recursion depth and storing the result. The recursion depth can go up to (N) in the worst case, and we store combinations in the result list.

Code

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

        def dfs(i, curr_sum, curr):
            if curr_sum == 0:
                res.append(curr)
                return
            if curr_sum < 0 or i >= N:
                return

            for j in range(i, N):
                if j > i and candidates[j] == candidates[j - 1]:
                    continue
                dfs(j + 1, curr_sum - candidates[j], curr + [candidates[j]])

        dfs(0, target, [])
        return res

Editorial

class Solution:
    def combinationSum2(self, candidates, target):
        answer = []
        candidates.sort()
        self.backtrack(candidates, target, 0, [], answer)
        return answer

    def backtrack(self, candidates, target, totalIdx, path, answer):
        if target < 0:
            return  # backtracking
        if target == 0:
            answer.append(path)
            return  # end
        for i in range(totalIdx, len(candidates)):
            if i > totalIdx and candidates[i] == candidates[i - 1]:
                continue
            self.backtrack(
                candidates,
                target - candidates[i],
                i + 1,
                path + [candidates[i]],
                answer,
            )