40. Combination Sum II
Model: qwen3.5:9b
Topics: Array,Backtracking
FAANG asked: 1
Acceptance rate: 50.4%
Problem Breakdown
We are given an array of candidate numbers (candidates) and a target sum (target). The goal is to find all unique combinations where the candidates add up exactly to target.
Key constraints:
- Each number in
candidatescan be used only once per combination (unlike Combination Sum I). - The output must not contain duplicate combinations, even if
candidatescontains duplicates.
Inputs are a list of integers and an integer target. Outputs is a list of lists. Implicitly, we need to handle cases where no solution exists or the input array is empty. Since order within a combination doesn’t matter (e.g., [1, 2] is same as [2, 1]), sorting helps us enforce canonical ordering and manage duplicates effectively.
Intuition
Initially, this looks like generating all subsets to check their sums. A brute-force approach would iterate through every possible subset () and sum them up. This fails for two reasons:
- It generates duplicate combinations if the input has repeated numbers (e.g.,
[1, 1]leading to multiple identical branches). - We can prune early; once a partial sum exceeds
target, we stop that branch immediately since all candidates are positive integers.
The key insight is sorting the array first. By sorting, duplicate values become adjacent. When backtracking through the recursion tree at any specific depth (level), if we encounter a number identical to the previous one at this same level, it means we have already explored that combination path starting with that value in the current iteration of the loop. Skipping these duplicates prevents generating redundant branches while still allowing us to use those values deeper down in other combinations where they were part of an earlier branch’s sum.
Approach
- Sort
candidatesfirst. This groups identical numbers and allows for easy duplicate skipping logic during recursion, as well as enabling early pruning when a value exceeds the remaining target (since subsequent values will also be larger). - Define a recursive helper function (
backtrack) that takes the current index (start_index) to avoid reusing elements from previous branches, and the remainingcurrent_targetsum needed. - In each step of the loop:
- If
candidates[i]equalscandidates[i-1], skip it if we are not at the very start of this recursion level (i.e.,start_index). This ensures uniqueness across combinations. - Add current number to path, subtract from target, and recurse with index
+ 1.
- If
- Base cases:
- If remaining target is 0, we found a valid combination; add copy of path to results.
- Optimization: Since the array is sorted, if
candidates[i] > current_target, all subsequent elements will also exceed it (or be equal), so we can break the loop immediately instead of continuing checks.
Complexity Analysis
- Time: where N is the number of candidates and S is the maximum size of a solution set in terms of valid combinations generated. In worst-case scenarios without duplicates pruning effectively, it approaches exponential time relative to input length due to backtracking (), but sorting + duplicate skipping significantly reduces this for inputs with many repeated values.
- Space: auxiliary space for the recursion stack depth (bounded by N) and output storage is excluded from standard complexity analysis unless specified as “total memory”.
Solution
from typing import List
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
# Sort to group duplicates and allow pruning logic
candidates.sort()
res = []
path = []
def backtrack(start_index, current_target):
if current_target == 0:
res.append(path[:])
return
for i in range(start_index, len(candidates)):
# Skip duplicates at the same recursion level to prevent duplicate combinations.
# We only skip if we are NOT starting a new branch (i > start_index)
# and current value matches previous one.
if i > start_index and candidates[i] == candidates[i - 1]:
continue
val = candidates[i]
# Pruning: If adding this number exceeds target, stop since array is sorted
if val <= current_target:
path.append(val)
backtrack(i + 1, current_target - val)
path.pop()
backtrack(0, target)
return res
Edge Cases Handled
- Empty Candidates: The loop range handles this gracefully (loop doesn’t run), returning empty list.
- Target Unreachable: If no combination sums to
target, the base case for sum==0 is never hit; returns empty result set. - Duplicate Inputs: Sorting groups them, and the condition
i > start_indexensures we only pick one branch per unique value at a specific depth level. - Single Element Matches Target: The logic correctly adds it to path when target becomes 0 before popping back up in recursion stack (handled by base case check).