Combination Sum II

Description

Combination Sum II
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.

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
• 1 <= target <= 30

Brute Force Approach: Standard Backtracking + HashSet Filtering

Intuition

Sort the array so combinations are constructed in order. Generate all valid combination paths down to target == 0 using standard i + 1 recursion, and insert each valid path into a HashSet to filter out duplicate combinations.

import java.util.*;
 
class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates); // Sort so duplicate paths generate identical list representations
        Set<List<Integer>> resultSet = new HashSet<>();
        backtrack(candidates, 0, target, new ArrayList<>(), resultSet);
        return new ArrayList<>(resultSet);
    }
 
    private void backtrack(int[] candidates, int start, int target, List<Integer> current, Set<List<Integer>> result) {
        if (target == 0) {
            result.add(new ArrayList<>(current));
            return;
        }
 
        for (int i = start; i < candidates.length; i++) {
            if (candidates[i] > target) {
                break; // Stop early if candidate exceeds target
            }
 
            current.add(candidates[i]);
            backtrack(candidates, i + 1, target - candidates[i], current, result); // i + 1 because element used once
            current.remove(current.size() - 1);
        }
    }
}
 

Complexity

• Time Complexity: $O(2^N\cdot N)$ — Explores up to $2^N$ candidate subsets, and inserting each into the hash set takes $O(N)$ time.
• Space Complexity: $O(2^N\cdot N)$ — High memory consumption due to storing duplicate combinations inside the HashSet.

---

Most Optimized Solution: Sorting + Backtracking Skip Rule

Intuition

Instead of collecting duplicate combinations and filtering them later with a set, prevent duplicate branches from executing at the same decision level:

1. **Sort candidates**: Group identical numbers together (e.g., [1, 1, 2, 5, 6, 7, 10]).
2. Skip Rule (i > start && candidates[i] == candidates[i - 1]):

• i == start: Pick the first occurrence of a number at the current position level.
• i > start: Skip identical adjacent numbers because that choice was already explored at this exact level.

3. **Pass i + 1**: Ensures each array index is used at most once.
4. Early Pruning (candidates[i] > target): Break out of the loop immediately because all subsequent numbers will also be too large.

candidates = [1, 1, 2, 5, 6, 7, 10], target = 8
 
                     target = 8
               /         |          \
            pick 1     pick 1      pick 2
          (index 0)  (index 1)   (index 2)
            /            \
        target 7       SKIP! (i > start && candidates[1] == candidates[0])
 

import java.util.*;
 
class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates); // Step 1: Group identical numbers together
        List<List<Integer>> result = new ArrayList<>();
        backtrack(candidates, 0, target, new ArrayList<>(), result);
        return result;
    }
 
    private void backtrack(int[] candidates, int start, int target, List<Integer> current, List<List<Integer>> result) {
        // Base Case: Match found
        if (target == 0) {
            result.add(new ArrayList<>(current));
            return;
        }
 
        for (int i = start; i < candidates.length; i++) {
            // Early Pruning: Sorted array means no larger number can fit
            if (candidates[i] > target) {
                break;
            }
 
            // Step 2: Skip identical elements at the SAME decision level
            if (i > start && candidates[i] == candidates[i - 1]) {
                continue;
            }
 
            current.add(candidates[i]);
            backtrack(candidates, i + 1, target - candidates[i], current, result); // i + 1: single use only
            current.remove(current.size() - 1); // Backtrack
        }
    }
}
 

Complexity

• Time Complexity: $O(2^N)$ — Generates only unique valid combinations without redundant recursive branches.
• Space Complexity: $O(N)$ — Maximum recursion stack depth (excluding the output list).

---

Easy Memory Rule

“For Combination Sum II: Sort first. Use i + 1 (use once). Skip duplicates with if (i > start && candidates[i] == candidates[i - 1]) continue;.”