loading

40. Combination Sum II — Step-by-Step Visualization

mediumLeetCode #40ArrayBacktracking

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] ] ```

Algorithm Pattern

Sorted Backtracking with Duplicate-Skip

Key Idea

Sorting the candidates array allows us to skip duplicate numbers easily. Within a recursive level, we only process the same digit once and then skip the rest of its occurrences to avoid building identical combinations with different instances of the same value.

Step-by-Step Approach

  1. Sort `candidates` in non-decreasing order.
  2. Define `dfs(index, currentTotal, currentCombination)`.
  3. Base Case: If `currentTotal == target`, add a unique combination to results.
  4. Iterate from the current `index` to the end of the array.
  5. If `candidates[i]` is a duplicate (`i > index` and `candidates[i] == candidates[i-1]`), skip it.
  6. If `candidates[i] + currentTotal > target`, we can break the loop early (as the array is sorted).
  7. Recurse into the NEXT index `i + 1` to ensure each number is used only once per combination.

Common Gotchas

  • The duplicate check `i > index` is critical—it ensures we still process the *first* instance of a duplicate at each level but skip the subsequent ones.
  • Failing to sort the array first will break the duplicate skipping logic and result in a bloated solution space.

Related Problems

← All problems