MEDIUM NC#75 Backtracking
40. Combination Sum II
📖 Problem
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. The solution set must not contain duplicate combinations.
🧠 Visual Learning Aid
1 Model the input into the right structure
2 Choose the core technique and invariant
3 Execute step-by-step with a sample
4 Validate complexity and edge cases
JS/TS Refreshers
- •Array methods (`push`, `pop`, `shift`, `slice`)
- •Object/Map/Set usage patterns
- •Function parameter and return typing
- •Recursive function frames
- •Push/pop state undo
- •Pruning branches early
Logical Thinking Concepts
- •Define invariants before coding
- •Check edge cases first (`[]`, single element, duplicates)
- •Estimate time/space before implementation
- •Apply Backtracking reasoning pattern
- •Apply Recursion reasoning pattern
💡 Approach
- → Sort candidates to avoid duplicates
- → Use backtracking to try all combinations
- → Skip duplicate candidates in same level
- → Time: O(2^n) in worst case, Space: O(n) for recursion
🧭 Prerequisites
🛠️ Hints & Pitfalls
Hints
- •Sort candidates to avoid duplicates
- •Use backtracking to try all combinations
- •Skip duplicate candidates in same level
Common Pitfalls
- •Time: O(2^n) in worst case, Space: O(n) for recursion
🧪 Test Cases
Test Case 1
Not run Input:
combinationSum2([10,1,2,7,6,1,5], 8); Expected:
[[1,1,6], [1,2,5], [1,7], [2,6]] Test Case 2
Not run Input:
combinationSum2([2,5,2,1,2], 5); Expected:
[[1,2,2], [5]] Test Case 3
Not run Input:
combinationSum2(candidates: number[], target: number); Expected:
Computed from hidden reference 📝 Code Editor
📤 Output