40. Combination Sum II - Detailed Explanation

Problem Statement

Given a collection of candidate numbers candidates (without duplicates) and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may only use each candidate once. The solution set must not contain duplicate combinations.

Examples

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

Constraints

• 1 ≤ candidates.length ≤ 100
• 1 ≤ candidates[i] ≤ 50
• All elements of candidates are integers (may contain duplicates)
• 1 ≤ target ≤ 500

Hints

• Sort candidates first to help skip duplicates.
• Use backtracking, advancing an index so each number is used at most once.
• When you see the same value at the same recursive depth, skip it to avoid duplicate sequences.

Approach 1 Backtracking with Pruning

Idea

We explore each number in sorted order, decide to include it or skip it, and recurse on the remaining target. By sorting we can easily detect and skip over duplicates at the same decision level.

Steps

1. Sort candidates.
2. Define a recursive function dfs(start, remaining, path):
   • If remaining == 0, record a copy of path.
   • Otherwise, for i from start to len(candidates)-1:
     • If candidates[i] > remaining, break (further ones are too big).
     • If i > start and candidates[i] == candidates[i-1], continue (skip duplicate).
     • Append candidates[i] to path, recurse dfs(i+1, remaining - candidates[i], path), then pop.
3. Call dfs(0, target, []) and return collected results.

Code (Python)

Code (Java)