Combination Sum II — Medium Problem & Solution

Problem statement

You are given a list of positive integers candidates (values may repeat) and a positive target. Return every distinct combination of candidates whose values add up to exactly target. Each position of candidates may be used at most once in a combination, so a value can appear in a combination at most as many times as it appears in the input.

Two combinations are the same if they hold the same values with the same multiplicities; list each only once. Write each combination in non-decreasing order and list the combinations in lexicographic order. If there is none, return an empty list.

Example 1

Input: candidates = [3,1,4,1,5,2], target = 6
Output: [[1,1,4],[1,2,3],[1,5],[2,4]]

Example 2

Input: candidates = [2,2,2,2], target = 5
Output: []
Explanation: Sums of 2s are always even.

Example 3

Input: candidates = [4,2,6], target = 6
Output: [[2,4],[6]]

Constraints

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

How to solve Combination Sum II

This is Subsets II restricted to subsets with the right sum: after sorting, skipping repeated values at the same depth makes each combination appear once, and the positive values let the search stop early.

Approach

1. Sort candidates.
2. dfs(start, remaining): if remaining == 0, record a copy of the path.
3. Otherwise for i from start: skip duplicates at this depth; if candidates[i] > remaining, stop the loop; else push it, call dfs(i + 1, remaining - candidates[i]), pop.
4. Return what was recorded.

Why it works

Moving to i + 1 uses each position at most once, and the duplicate skip lets only the leftmost copy of a value start a branch at a given depth, so each multiset is built exactly once. Values are tried in increasing order at every depth, and no combination is a prefix of another (all have the same positive sum), so the output comes out lexicographically sorted.

Complexity

• Time — O(2^n · n) in the worst case; the sum bound prunes most branches
• Space — O(target) recursion depth besides the output

Pitfalls

• Recursing on i instead of i + 1 reuses the same position (that is Combination Sum I).
• break rather than continue when a value is too big — the array is sorted, so the rest are too big as well.
• Return an empty list, not [[]], when nothing sums to the target.

Reference solution

Python

from typing import List

def combinationSum2(candidates: List[int], target: int) -> List[List[int]]:
    a = sorted(candidates)
    out = []
    path = []

    def dfs(start, rem):
        if rem == 0:
            out.append(path[:])
            return
        for i in range(start, len(a)):
            if i > start and a[i] == a[i - 1]:
                continue
            if a[i] > rem:
                break
            path.append(a[i])
            dfs(i + 1, rem - a[i])
            path.pop()

    dfs(0, target)
    return out

JavaScript

var combinationSum2 = function(candidates, target) {
    var a = candidates.slice().sort(function(x, y) { return x - y; });
    var out = [];
    var path = [];
    var dfs = function(start, rem) {
        if (rem === 0) {
            out.push(path.slice());
            return;
        }
        for (var i = start; i < a.length; i++) {
            if (i > start && a[i] === a[i - 1]) continue;
            if (a[i] > rem) break;
            path.push(a[i]);
            dfs(i + 1, rem - a[i]);
            path.pop();
        }
    };
    dfs(0, target);
    return out;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Non-decreasing Subsequences Medium
• Construct the Lexicographically Largest Valid Sequence Medium
• Matchsticks to Square Medium
• Combination Sum III Medium
• Permutations II Medium
• Subsets II Medium