Combination Sum II

Mediumbacktrackingrecursion
Category: Backtracking
Companies that ask this question:
AmazonFacebookGoogle
LeetCode →NeetCode →

Approach

Combination Sum II

Problem Statement

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.

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

Intuition

Similar to Combination Sum I, but:

  • Cannot reuse same element (use each once)
  • Array has duplicates (need to skip)

Solution:

  1. Sort to group duplicates
  2. Skip duplicates at same level
  3. Move to next index (i+1, not i)

Pattern Recognition

This is Backtracking with Target + Duplicates:

  • Target sum constraint
  • No element reuse
  • Duplicate handling

Approach

def backtrack(start, current, total):
  if total == target:
    result.append(current.copy())
    return
  if total > target:
    return

  for i in range(start, len(candidates)):
    # Skip duplicates at same level
    if i > start and candidates[i] == candidates[i-1]:
      continue

    current.append(candidates[i])
    backtrack(i + 1, current, total + candidates[i])  # i+1, not i
    current.pop()

Key differences:

  • Pass i+1 (no reuse)
  • Skip duplicates with sorted array

Complexity Analysis

  • Time: O(2^n)
  • Space: O(n) recursion depth

Solution

java
1import java.util.*;
2
3class Solution {
4    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
5        List<List<Integer>> result = new ArrayList<>();
6        Arrays.sort(candidates);  // Sort to handle duplicates
7        backtrack(0, candidates, target, new ArrayList<>(), 0, result);
8        return result;
9    }
10
11    private void backtrack(int start, int[] candidates, int target,
12                          List<Integer> current, int total,
13                          List<List<Integer>> result) {
14        if (total == target) {
15            result.add(new ArrayList<>(current));
16            return;
17        }
18        if (total > target) {
19            return;
20        }
21
22        for (int i = start; i < candidates.length; i++) {
23            // Skip duplicates at same level
24            if (i > start && candidates[i] == candidates[i - 1]) {
25                continue;
26            }
27
28            current.add(candidates[i]);
29            backtrack(i + 1, candidates, target, current, total + candidates[i], result);
30            current.remove(current.size() - 1);
31        }
32    }
33}
34
Loading visualizer...