Combination Sum II

Combination Sum II

What is this problem about?

The Combination Sum II coding problem is a variation of the first Combination Sum problem with two major changes:

1. Each number in the candidate list may only be used once per combination.
2. The candidate list itself may contain duplicate numbers. The goal remains the same: find all unique combinations that sum up to a target. Because of the duplicates in the input, you must be extra careful not to produce duplicate combinations in the output.

Why is this asked in interviews?

Uber, Microsoft, and Tesla use the Combination Sum II interview question to test a candidate's ability to handle edge cases in backtracking. It requires more sophisticated logic than the first version because you must decide which instances of a duplicate number to include. It’s a perfect test of whether a candidate can "de-duplicate" a search space efficiently.

Algorithmic pattern used

The pattern is Backtracking with Sorting and Deduplication:

1. Sort the candidates first.
2. In the backtracking loop, if the current candidate is the same as the previous one at the same recursion level, skip it.
3. Increment the index in every recursive call to ensure each element is used at most once.

Example explanation

Candidates: [10, 1, 2, 7, 6, 1, 5], Target: 8 Sorted: [1, 1, 2, 5, 6, 7, 10]

1. Start at index 0 (value 1).
2. Level 1: Pick index 0 (1).
3. Level 2: Pick index 1 (1). Next combinations must sum to 8 - 1 - 1 = 6.
4. Level 2: If we had skipped index 0 and picked index 1, it would still be a 1. To avoid a duplicate search, we skip any candidates[i] == candidates[i-1] if we didn't pick i-1. This ensures we only start a combination with the first available instance of a duplicate number.

Common mistakes candidates make

• Using a Set for results: While technically correct, it's inefficient. Interviewers prefer you to prune the recursion so that duplicates are never generated in the first place.
• Forgetting to Sort: The de-duplication logic (cand[i] == cand[i-1]) only works if the array is sorted.
• Reusing elements: Not incrementing the index for the next recursive call.

Interview preparation tip

Master the logic of if (i > start && candidates[i] == candidates[i-1]) continue;. This is a standard way to handle duplicates in many backtracking problems (like Subsets II or Permutations II).