💬 Discord
Sign In
NeetCode #490LC-40MediumBacktrackingNC 150NC 250
← Back to All Problems

#490 · #40 · Combination Sum II(组合总和 II)

📌 Problem Statement & Constraints

Given a collection of candidate numbers candidates (which may contain duplicates) and a target, return all unique combinations summing to the target, where each candidate may be used at most once. Constraints: 1 <= candidates.length <= 100, 1 <= candidates[i] <= 50, 1 <= target <= 30.

💡 Core Algorithmic Approaches

  1. Sort the array so duplicates are adjacent, then use a loop-based backtrack that advances to i + 1 (each element used once).
  2. Deduplicate at each recursion level by skipping a candidate equal to its predecessor in the same loop.
  3. The key distinction: skipping equal values within one level removes duplicate combinations, while equal values in different levels are allowed.
  4. Pruning with candidates[j] > remain is valid after sorting.

💻 Benchmark Python3 Implementation

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

        def dfs(start: int, path: List[int], remain: int) -> None:
            if remain == 0:
                res.append(path[:])
                return
            for j in range(start, len(candidates)):
                # skip duplicates at THIS level (not across levels)
                if j > start and candidates[j] == candidates[j - 1]:
                    continue
                if candidates[j] > remain:
                    break                  # sorted -> no later value fits either
                path.append(candidates[j])
                dfs(j + 1, path, remain - candidates[j])   # each used once
                path.pop()

        dfs(0, [], target)
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(2^n) worst case, bounded by the number of valid combinations.
💾 Space Complexity
O(n) for the recursion path.

⚠️ Interview Pitfalls & Follow-ups

  • Using j > 0 instead of j > start in the duplicate skip: that would wrongly skip values that are legitimately repeated across different levels.
  • Not sorting: duplicates would not be adjacent and the skip would not work.
  • Advancing to j instead of j + 1: elements could be reused, contradicting the statement.
  • Using continue instead of break for the pruning: break is valid because the array is sorted, and it is much faster.