Combination Sum II

Combination Sum II mixes two tricky rules at once. Each number may be used only once, and the array can have duplicates. So you must move forward each step and also dodge repeated combinations. This pairs the no-reuse idea with the sort-then-skip idea. Get both right together and you have shown real backtracking control.

🎯 The Problem

You get an array that may contain duplicate numbers and a target, and you find every combination that adds up to the target. Here are the rules.

• Find every combination of numbers that adds up to the target.
• Each number at each position may be used only once.
• No combination may appear twice in the answer.
• The order inside a combination does not matter.

Let us say the array is [10, 1, 2, 7, 6, 1, 5] and the target is 8. Now 1 + 7 works. So does 1 + 2 + 5. So does 2 + 6. And 1 + 1 + 6 works using both of the 1 values. Each value is used as many times as it appears, no more.

Input:  candidates = [10, 1, 2, 7, 6, 1, 5], target = 8
Output: [[1,1,6], [1,2,5], [1,7], [2,6]]

Explanation: each number used at most as many times as it appears, no duplicate combinations.

Here is the danger. The two 1 values can each start a 1 + 7 branch. Both give the same combination, so one must be skipped.

🐢 Approach 1: Build Every Subset Then Filter (Brute Force)

The idea in one line: make every possible subset, then keep the ones that sum to the target.

How it works:

• List every subset of the array, like the power set.
• Add up each subset.
• Keep the subsets whose sum equals the target.
• Sort each kept subset and drop repeats so no combination appears twice.

Why it is weak:

• There are 2 to the power n subsets, and you build all of them.
• You also spend extra work removing duplicate combinations at the end.
• So it is slow and wasteful. The pruning ideas below are never used.

Here is the brute-force subset code for that idea:

def combination_sum2(candidates, target):
    result = set()

    def dfs(index, path):
        if index == len(candidates):
            if sum(path) == target:
                result.add(tuple(sorted(path)))
            return
        dfs(index + 1, path)
        dfs(index + 1, path + [candidates[index]])

    dfs(0, [])
    return [list(item) for item in sorted(result)]

⚡ Approach 2: Sort, Move Forward, Skip Equal Siblings (Best)

The idea in one line: sort, never reuse a position, and skip a repeated value at the same level.

Move forward (no reuse):

• Each number may be used only once.
• Pass i + 1 to the recursion, not i, so the current position is not picked again.
• That is the one difference from Combination Sum, where we passed i to allow reuse.

Sort and skip (no duplicate combinations):

• Sort the array so equal values sit together.
• At one level, the first copy of a value already explores every combination starting with it.
• A second equal copy at the same level would only repeat those, so skip it.
• The test is “i greater than start and this value equals the previous value.”
• Sorting is the only reason a simple previous-value check works.

Siblings versus children:

• Same i > start guard as Subsets II.
• We skip an equal sibling but still allow an equal value deeper in the path.
• So [1, 1, 6] is valid. The second 1 is a child of the first, not a sibling.
• But a second [1, 7] started by the sibling 1 is blocked.

Why it is fast:

• The early break on a too-big value and the duplicate skip prune whole branches.
• So real runs are usually far below the worst case.

This dry run on the sorted array shows the forward move and the skip together.

Steps to Solve

1. Sort the array so equal numbers sit next to each other.
2. Create a result list and a path for the current combination.
3. Start a recursive helper with the full target and start index 0.
4. If the remaining target is 0, record a copy of the path and return.
5. Loop from the start index. If the current value is bigger than the remaining target, stop the loop early.
6. If i > start and the current value equals the previous value, skip it with continue.
7. Add the value to the path, then recurse with i + 1 so the value is not reused.
8. Remove the value you just added. This is the un-choose step.

#include <stdio.h>

int cand[] = {10, 1, 2, 7, 6, 1, 5};
int n = 7;
int path[20];

void printCombo(int len) {
    printf("[");
    for (int i = 0; i < len; i++) {
        printf("%d", path[i]);
        if (i < len - 1) printf(",");
    }
    printf("]\n");
}

void backtrack(int start, int remain, int len) {
    if (remain == 0) { printCombo(len); return; }     // exact match
    for (int i = start; i < n; i++) {
        if (cand[i] > remain) break;                  // sorted, so stop early
        if (i > start && cand[i] == cand[i - 1])      // skip equal sibling
            continue;
        path[len] = cand[i];                          // choose
        backtrack(i + 1, remain - cand[i], len + 1);  // i+1 = no reuse
        // overwrite next loop = un-choose
    }
}

int main(void) {
    for (int a = 0; a < n; a++)
        for (int b = 0; b < n - 1; b++)
            if (cand[b] > cand[b + 1]) {
                int t = cand[b]; cand[b] = cand[b + 1]; cand[b + 1] = t;
            }
    backtrack(0, 8, 0);
    return 0;
}

[1,1,6]
[1,2,5]
[1,7]
[2,6]

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

vector<vector<int>> result;
vector<int> path;

void backtrack(vector<int>& cand, int start, int remain) {
    if (remain == 0) { result.push_back(path); return; }   // exact match
    for (int i = start; i < (int)cand.size(); i++) {
        if (cand[i] > remain) break;                        // sorted, stop early
        if (i > start && cand[i] == cand[i - 1]) continue;  // skip equal sibling
        path.push_back(cand[i]);                            // choose
        backtrack(cand, i + 1, remain - cand[i]);           // i+1 = no reuse
        path.pop_back();                                    // un-choose
    }
}

int main() {
    vector<int> cand = {10, 1, 2, 7, 6, 1, 5};
    sort(cand.begin(), cand.end());                         // duplicates become neighbours
    backtrack(cand, 0, 8);
    for (auto& c : result) {
        cout << "[";
        for (int i = 0; i < (int)c.size(); i++) {
            cout << c[i];
            if (i < (int)c.size() - 1) cout << ",";
        }
        cout << "]" << endl;
    }
    return 0;
}

[1,1,6]
[1,2,5]
[1,7]
[2,6]

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class CombinationSumII {
    static List<List<Integer>> result = new ArrayList<>();
    static List<Integer> path = new ArrayList<>();

    static void backtrack(int[] cand, int start, int remain) {
        if (remain == 0) { result.add(new ArrayList<>(path)); return; } // exact
        for (int i = start; i < cand.length; i++) {
            if (cand[i] > remain) break;                          // sorted, stop early
            if (i > start && cand[i] == cand[i - 1]) continue;    // skip equal sibling
            path.add(cand[i]);                                    // choose
            backtrack(cand, i + 1, remain - cand[i]);             // i+1 = no reuse
            path.remove(path.size() - 1);                         // un-choose
        }
    }

    public static void main(String[] args) {
        int[] cand = {10, 1, 2, 7, 6, 1, 5};
        Arrays.sort(cand);                                        // duplicates become neighbours
        backtrack(cand, 0, 8);
        System.out.println(result);
    }
}

[[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]

def combination_sum2(candidates, target):
    candidates.sort()                   # duplicates become neighbours
    result = []
    path = []

    def backtrack(start, remain):
        if remain == 0:                 # exact match found
            result.append(path[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remain:  # sorted, so nothing further fits
                break
            if i > start and candidates[i] == candidates[i - 1]:  # skip equal sibling
                continue
            path.append(candidates[i])                 # choose
            backtrack(i + 1, remain - candidates[i])   # i+1 = no reuse
            path.pop()                                 # un-choose

    backtrack(0, target)
    return result


print(combination_sum2([10, 1, 2, 7, 6, 1, 5], 8))

[[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]

function combinationSum2(candidates, target) {
  candidates.sort((a, b) => a - b);     // duplicates become neighbours
  const result = [];
  const path = [];

  function backtrack(start, remain) {
    if (remain === 0) {                 // exact match found
      result.push([...path]);
      return;
    }
    for (let i = start; i < candidates.length; i++) {
      if (candidates[i] > remain) break;                       // nothing further fits
      if (i > start && candidates[i] === candidates[i - 1]) continue; // skip equal sibling
      path.push(candidates[i]);                 // choose
      backtrack(i + 1, remain - candidates[i]); // i+1 = no reuse
      path.pop();                               // un-choose
    }
  }

  backtrack(0, target);
  return result;
}

console.log(JSON.stringify(combinationSum2([10, 1, 2, 7, 6, 1, 5], 8)));

[[1,1,6],[1,2,5],[1,7],[2,6]]

Let us walk through the Python version line by line, because two rules run side by side here.

candidates.sort() puts equal values next to each other. Both the early-stop and the duplicate-skip depend on the array being sorted.

if remain == 0 records a copy of the path and returns when the picks hit the target exactly.

for i in range(start, len(candidates)) loops from the start index forward. We never look before start, which keeps combinations in one order.

if candidates[i] > remain: break is an early stop. Because the array is sorted, once a value is bigger than what is left, every value after it is also too big. So we break out of the loop entirely, which saves work.

if i > start and candidates[i] == candidates[i - 1]: continue is the duplicate skip. The i > start part means we are past the first choice at this level. The equality part means this value matches its left neighbour. Together they catch a repeated sibling and skip it, so the same combination is not built twice. The first copy at a level still runs, because there i equals start.

path.append(candidates[i]) chooses the value.

backtrack(i + 1, remain - candidates[i]) explores deeper. Here we pass i + 1, not i. That moves us forward, so the current position is never reused. This is the no-reuse rule.

path.pop() un-chooses, resetting the path for the next sibling.

⏱️ Time and Space Complexity

In the worst case the search explores many subsets, so the time is exponential, around O(2^n) over n candidates. The sort adds O(n log n), which is small. The duplicate skip and the early break prune branches, so real runs are usually much faster than the worst case. The extra space is O(n) for the recursion depth and the path.

🧩 Key Takeaways

• ✅ Each number may be used only once, so recurse with i + 1, not i.
• ✅ The array can have duplicates, so sort first to make equal values neighbours.
• ✅ Skip an equal sibling with the i > start and equal-previous test.
• ✅ The early break on a too-big value prunes the search once the array is sorted.
• ✅ An equal value deeper in the path is fine, like the second 1 in [1,1,6].

🚀 What’s Next?

• Permutations
• Subsets II