Backtracking with Duplicate Skipping — Clean Solution to Combination Sum II

Backtracking with Duplicate Skipping — Clean Solution to Combination Sum II

Author

Affiliation

Kim Hung Bui

Leetcode - 40. Combination Sum 2

1 Intuition

The problem asks us to find unique combination that sum to a garget, but each number can be used only once. This immediately suggests a backtracking appoach - we explore combinations recursively and prune paths that exceed the target.

Because there may be duplicate numbers in the input, we need to skip duplicates at the same depth to avoid generating repeated combinations.

2 Approach

1. Sort the input to bring duplicates together and allow early stopping.

2. Use a backtracking finction to explore choices:

   • Include current number
   • Recurse with the next index (i+1) to prevent resuing the same element

3. At each rescursive call:

   • if total == target, we’ve found a valid path - store it
   • if total > target, stop this path
   • Skip current element if it’s a duplicate at the same recursion level.

3 Complexity

• Time complexity: \(O(2^n)\) in the worst case, due to the number of combinations we exlore (through pruning and skipping duplicates improve this).

• Space complexity: \(O(n)\) for the rescursion call stack and current path.

4 Code

from typing import List

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

    result = []
    def backtrack(start: int, path: List[int], total: int):
        if total == target:
            result.append(path[:])
            return
        if total > target:
            return

        for i in range(start, len(candidates)):
            cur = candidates[i]

            # skip duplicates at the same depth level
            if cur == prev:
                continue
            if total + cur > target:
                break

            path.append(cur)
            backtrack(i + 1, path, total + cur)
            path.pop()
            prev = cur

    backtrack(0, [], 0)
    return result