Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Combination Sum II

MEDIUMProblemSolveExternal Links

Description

You are given an array of integers called candidates and an integer target. Your task is to find all unique combinations of numbers from candidates that add up to target.

The key rules are:

  • Each number in candidates may only be used once per combination (but the array may contain duplicates of the same value, and each copy is treated as a separate element that can be independently included).
  • The solution set must not contain duplicate combinations. Two combinations are considered duplicates if they contain the same numbers in the same quantities, regardless of the order of selection.

Return all such unique combinations. The combinations may be returned in any order, and the numbers within each combination may be in any order.

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

Explanation: After sorting: [1, 1, 2, 5, 6, 7, 10]. We need groups that sum to 8:

  • [1, 1, 6]: uses both copies of 1 plus 6 → 1+1+6 = 8 ✓
  • [1, 2, 5]: uses one copy of 1, then 2 and 5 → 1+2+5 = 8 ✓
  • [1, 7]: uses one copy of 1 plus 7 → 1+7 = 8 ✓
  • [2, 6]: 2+6 = 8 ✓

Note that [1, 2, 5] appears only once even though there are two 1's we could choose from. Picking the first 1 or the second 1 yields the same combination.

Example 2

Input: candidates = [2, 5, 2, 1, 2], target = 5

Output: [[1, 2, 2], [5]]

Explanation: After sorting: [1, 2, 2, 2, 5]. Two unique ways to reach 5:

  • [1, 2, 2]: 1+2+2 = 5 ✓ (uses two of the three available 2's)
  • [5]: a single element that equals the target ✓

Combinations like [2, 2, 1] are the same as [1, 2, 2] (just reordered), so we only count it once.

Example 3

Input: candidates = [3, 8], target = 7

Output: []

Explanation: No subset of [3, 8] sums to 7. 3 alone is too small, 8 alone is too large, and 3+8 = 11 overshoots. An empty list is returned.

Constraints

  • 1 ≤ candidates.length ≤ 100
  • 1 ≤ candidates[i] ≤ 50
  • 1 ≤ target ≤ 30

Editorial

Brute Force

Intuition

The most straightforward way to find all combinations that sum to a target is to generate every possible subset of the candidates array and check each subset's sum.

Imagine you have a bag of numbered balls. The brute force approach is to lay out every possible handful of balls (every subset), add up the numbers on each handful, and keep only the handfuls whose total equals the target. To avoid duplicate handfuls, you store each qualifying subset in a set (after sorting it) so that identical combinations are automatically de-duplicated.

For an array of length n, there are 2^n possible subsets. We generate each one, compute its sum, and if it equals the target, we add it (sorted) to a result set.

This is extremely wasteful because we never prune our search — we blindly generate and evaluate every subset even if the sum has already exceeded the target.

Step-by-Step Explanation

Let's trace through with candidates = [2, 5, 2, 1, 2], target = 5.

After sorting: [1, 2, 2, 2, 5]. We enumerate all 2^5 = 32 subsets:

Step 1: Subset [] → sum = 0. Not equal to 5. Skip.

Step 2: Subset [1] → sum = 1. Not equal to 5. Skip.

Step 3: Subset [2] → sum = 2. Not equal to 5. Skip.

Step 4: Subset [1, 2] → sum = 3. Not equal to 5. Skip.

Step 5: Subset [2, 2] → sum = 4. Not equal to 5. Skip.

Step 6: Subset [1, 2, 2] → sum = 5. Equals target! Add sorted combo [1, 2, 2] to result set.

Step 7: Subset [2, 2, 2] → sum = 6. Exceeds target. Skip.

Step 8: Subset [1, 2, 2, 2] → sum = 7. Exceeds target. Skip.

Step 9: (many more subsets checked...) Subset [5] → sum = 5. Equals target! Add [5] to result set.

Step 10: Continue through remaining subsets. Some produce duplicate [1, 2, 2] from different index selections — the set automatically de-duplicates.

Result: [[1, 2, 2], [5]]. We checked all 32 subsets to find just 2 valid ones.

Algorithm

  1. Sort the candidates array.
  2. Generate all 2^n subsets of the array using bit manipulation or recursion.
  3. For each subset, compute its sum.
  4. If the sum equals the target, sort the subset and add it to a result set (to de-duplicate).
  5. Convert the result set to a list and return it.

Code

#include <vector>
#include <set>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        int n = candidates.size();
        set<vector<int>> resultSet;
        
        for (int mask = 0; mask < (1 << n); mask++) {
            vector<int> subset;
            int sum = 0;
            for (int i = 0; i < n; i++) {
                if (mask & (1 << i)) {
                    subset.push_back(candidates[i]);
                    sum += candidates[i];
                }
            }
            if (sum == target) {
                sort(subset.begin(), subset.end());
                resultSet.insert(subset);
            }
        }
        
        return vector<vector<int>>(resultSet.begin(), resultSet.end());
    }
};
class Solution:
    def combinationSum2(self, candidates: list[int], target: int) -> list[list[int]]:
        candidates.sort()
        n = len(candidates)
        result_set = set()
        
        for mask in range(1 << n):
            subset = []
            total = 0
            for i in range(n):
                if mask & (1 << i):
                    subset.append(candidates[i])
                    total += candidates[i]
            if total == target:
                result_set.add(tuple(sorted(subset)))
        
        return [list(combo) for combo in result_set]
import java.util.*;

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        int n = candidates.length;
        Set<List<Integer>> resultSet = new HashSet<>();
        
        for (int mask = 0; mask < (1 << n); mask++) {
            List<Integer> subset = new ArrayList<>();
            int sum = 0;
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    subset.add(candidates[i]);
                    sum += candidates[i];
                }
            }
            if (sum == target) {
                Collections.sort(subset);
                resultSet.add(subset);
            }
        }
        
        return new ArrayList<>(resultSet);
    }
}

Complexity Analysis

Time Complexity: O(2^n × n)

We generate all 2^n subsets. For each subset, we iterate through all n elements to build it and compute its sum, taking O(n) time. Sorting each qualifying subset is also O(n log n) but dominated by the enumeration. Total: O(2^n × n).

With n up to 100, 2^100 is astronomically large — this approach is completely impractical for the given constraints.

Space Complexity: O(2^n × n)

In the worst case, we store up to 2^n subsets in the result set, each of length up to n.

Why This Approach Is Not Efficient

The brute force generates all 2^n subsets regardless of whether they can possibly sum to the target. With n up to 100, 2^100 ≈ 1.27 × 10^30 subsets — far beyond any reasonable computation limit.

The core problem is the lack of pruning: we never abandon a path early even when the running sum already exceeds the target. If we sort the array and build subsets incrementally, we can stop exploring a branch the moment the partial sum exceeds the target. This insight leads to a backtracking approach where we recursively build combinations and prune impossible branches.

Additionally, using a set for de-duplication is wasteful. If we handle duplicates during the search itself (by skipping over repeated values at the same decision level), we avoid generating duplicates in the first place rather than filtering them out afterward.

Optimal Approach - Sorting + Backtracking with Pruning

Intuition

Instead of generating all subsets and checking them, we build combinations incrementally using backtracking, making decisions one element at a time and abandoning paths that cannot succeed.

Picture yourself at a buffet with a limited budget (the target). The dishes are laid out in order from cheapest to most expensive (we sort the array). You walk along the line making choices:

  • Include this dish and reduce your remaining budget, then continue choosing from the remaining dishes.
  • Skip this dish and move to the next one.
  • Stop entirely if the cheapest remaining dish already exceeds your remaining budget — nothing beyond it can help.

The trick for avoiding duplicate meals (combinations) is: when you are at the same decision point and see multiple copies of the same dish, you only consider the first copy. If you skip the first copy, there is no reason to try the second copy — it would produce an identical selection.

Formally:

  1. Sort the candidates array.
  2. Use recursive backtracking with a start index and a remaining sum.
  3. At each recursive call, iterate from start to end. For each candidate:
    • If it exceeds the remaining sum, prune (break out of the loop — everything after is ≥ this value).
    • If it is the same as the previous candidate at this same recursion level (and is not the first element at this level), skip it to avoid duplicates.
    • Otherwise, include it, recurse with start = current_index + 1 and remaining - candidate, then backtrack (remove it).

Step-by-Step Explanation

Let's trace through candidates = [2, 5, 2, 1, 2], target = 5.

After sorting: [1, 2, 2, 2, 5].

Step 1: Start backtracking with path = [], remaining = 5, start = 0.

Step 2: Try index 0: candidate = 1. Include it. path = [1], remaining = 4, recurse from index 1.

Step 3: Try index 1: candidate = 2. Include it. path = [1, 2], remaining = 2, recurse from index 2.

Step 4: Try index 2: candidate = 2. Include it. path = [1, 2, 2], remaining = 0. Remaining is 0 — found valid combination! Record [1, 2, 2]. Backtrack: remove 2, path = [1, 2].

Step 5: Try index 3: candidate = 2. But candidates[3] == candidates[2] and 3 > 2 (same recursion level). Skip this duplicate.

Step 6: Try index 4: candidate = 5. 5 > remaining (2). Prune — break the loop. Backtrack: remove 2, path = [1].

Step 7: Back at recursion level for path = [1], try index 2: candidate = 2. But candidates[2] == candidates[1] and 2 > 1. Skip duplicate.

Step 8: Try index 3: candidate = 2. But candidates[3] == candidates[2] and 3 > 1. Skip duplicate.

Step 9: Try index 4: candidate = 5. 5 > remaining (4). Prune. Backtrack: remove 1, path = [].

Step 10: Back at root level, try index 1: candidate = 2. Include it. path = [2], remaining = 3, recurse from index 2.

Step 11: Try index 2: candidate = 2. Include it. path = [2, 2], remaining = 1, recurse from index 3.

Step 12: Try index 3: candidate = 2. 2 > remaining (1). Prune. Backtrack: remove 2, path = [2].

Step 13: Try index 3: candidate = 2. Same as candidates[2] and 3 > 2. Skip duplicate. Try index 4: candidate = 5. 5 > remaining (3). Prune. Backtrack: remove 2, path = [].

Step 14: Back at root, try index 2: candidate = 2. Same as candidates[1] and 2 > 0. Skip. Same for index 3. Try index 4: candidate = 5. Include it. path = [5], remaining = 0. Found! Record [5]. Backtrack.

Result: [[1, 2, 2], [5]].

Backtracking — Building Combinations with Pruning and Duplicate Skipping — Watch how the sorted array enables us to prune branches early (when the next candidate exceeds remaining) and skip duplicates at the same recursion level to avoid repeated work.

Algorithm

  1. Sort the candidates array in ascending order.
  2. Initialize an empty result list and an empty current path list.
  3. Define a recursive function backtrack(start, remaining):
    a. If remaining == 0, append a copy of the current path to results and return.
    b. Iterate i from start to end of array:
    • If candidates[i] > remaining, break (pruning: all subsequent elements are ≥ this one).
    • If i > start and candidates[i] == candidates[i-1], continue (skip duplicate at same level).
    • Append candidates[i] to the path.
    • Recurse with backtrack(i + 1, remaining - candidates[i]).
    • Pop the last element from the path (backtrack).
  4. Call backtrack(0, target) and return the result list.

Code

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<vector<int>> result;
        vector<int> path;
        backtrack(candidates, target, 0, path, result);
        return result;
    }
    
    void backtrack(vector<int>& candidates, int remaining, int start,
                   vector<int>& path, vector<vector<int>>& result) {
        if (remaining == 0) {
            result.push_back(path);
            return;
        }
        
        for (int i = start; i < candidates.size(); i++) {
            if (candidates[i] > remaining) break;
            if (i > start && candidates[i] == candidates[i - 1]) continue;
            
            path.push_back(candidates[i]);
            backtrack(candidates, remaining - candidates[i], i + 1, path, result);
            path.pop_back();
        }
    }
};
class Solution:
    def combinationSum2(self, candidates: list[int], target: int) -> list[list[int]]:
        candidates.sort()
        result = []
        path = []
        
        def backtrack(start: int, remaining: int) -> None:
            if remaining == 0:
                result.append(path[:])
                return
            
            for i in range(start, len(candidates)):
                if candidates[i] > remaining:
                    break
                if i > start and candidates[i] == candidates[i - 1]:
                    continue
                
                path.append(candidates[i])
                backtrack(i + 1, remaining - candidates[i])
                path.pop()
        
        backtrack(0, target)
        return result
import java.util.*;

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        backtrack(candidates, target, 0, path, result);
        return result;
    }
    
    private void backtrack(int[] candidates, int remaining, int start,
                           List<Integer> path, List<List<Integer>> result) {
        if (remaining == 0) {
            result.add(new ArrayList<>(path));
            return;
        }
        
        for (int i = start; i < candidates.length; i++) {
            if (candidates[i] > remaining) break;
            if (i > start && candidates[i] == candidates[i - 1]) continue;
            
            path.add(candidates[i]);
            backtrack(candidates, remaining - candidates[i], i + 1, path, result);
            path.remove(path.size() - 1);
        }
    }
}

Complexity Analysis

Time Complexity: O(2^n)

In the worst case, we may still explore an exponential number of branches. Each element has two choices: include or skip. The pruning (early termination when sum exceeds target) and duplicate skipping significantly reduce the actual number of explored nodes in practice, but the theoretical upper bound remains O(2^n) where n is the length of candidates. Sorting takes O(n log n) which is dominated by the exponential search.

Given the constraints (n ≤ 100, values ≤ 50, target ≤ 30), the effective search space is much smaller because the small target (≤ 30) and the minimum value (≥ 1) mean combinations have at most 30 elements, and pruning cuts branches aggressively.

Space Complexity: O(n)

The recursion stack depth is at most n (one call per candidate element). The current path also holds at most n elements. The output list is not counted toward auxiliary space. Total auxiliary space: O(n).