Combination Sum II

Medium Problem 89 of 151 Java and Python

Problem

Given a collection of candidate numbers candidates (which may contain duplicates) and a target, find all unique combinations that sum to target.

Each number may be used only once in a combination, and the answer 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

Explanation

Combine two ideas you have already seen: recurse with i + 1 because each element is used at most once (Subsets), and skip equal values at the same depth to avoid duplicate combinations (Subsets II).

Approach 1 · Naive

Every subset, filter and deduplicate

Time O(n · 2ⁿ)
Space O(n) recursion plus the set

Generate all subsets of the sorted array, keep those summing to the target, and remove duplicates with a set. Only workable for small inputs (2ⁿ subsets).

Sort and enumerate subsets with a take/skip recursion.
When the sum equals the target, add the subset to a set.

Java

import java.util.*;

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        Set<List<Integer>> found = new HashSet<>();
        search(candidates, 0, target, new ArrayList<>(), found);
        return new ArrayList<>(found);
    }

    private void search(int[] c, int i, int remaining, List<Integer> path, Set<List<Integer>> found) {
        if (remaining == 0) {
            found.add(new ArrayList<>(path));
            return;
        }
        if (i == c.length || remaining < 0) {
            return;
        }
        path.add(c[i]);
        search(c, i + 1, remaining - c[i], path, found);
        path.remove(path.size() - 1);
        search(c, i + 1, remaining, path, found);
    }
}

Python

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        c = sorted(candidates)
        found, path = set(), []

        def search(i, remaining):
            if remaining == 0:
                found.add(tuple(path))
                return
            if i == len(c) or remaining < 0:
                return
            path.append(c[i])
            search(i + 1, remaining - c[i])
            path.pop()
            search(i + 1, remaining)

        search(0, target)
        return [list(t) for t in found]

Approach 2 · Optimal

Sorted backtracking, skip duplicates

Time O(n · 2ⁿ) worst case, far less with pruning
Space O(n) recursion

Sort. At each depth, skip a value equal to the previous one in the loop, stop when values exceed the remaining target, and recurse with i + 1.

Sort candidates.
backtrack(start, remaining): if remaining == 0, record.
For i from start: skip if i > start and c[i] == c[i - 1]; break if c[i] > remaining; push, recurse with (i + 1, remaining - c[i]), pop.

Java

import java.util.*;

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> result = new ArrayList<>();
        backtrack(candidates, 0, target, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(int[] c, int start, int remaining, List<Integer> path, List<List<Integer>> result) {
        if (remaining == 0) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < c.length && c[i] <= remaining; i++) {
            if (i > start && c[i] == c[i - 1]) {
                continue;
            }
            path.add(c[i]);
            backtrack(c, i + 1, remaining - c[i], path, result);
            path.remove(path.size() - 1);
        }
    }
}

Python

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        c = sorted(candidates)
        result, path = [], []

        def backtrack(start, remaining):
            if remaining == 0:
                result.append(path[:])
                return
            for i in range(start, len(c)):
                if i > start and c[i] == c[i - 1]:
                    continue
                if c[i] > remaining:
                    break
                path.append(c[i])
                backtrack(i + 1, remaining - c[i])
                path.pop()

        backtrack(0, target)
        return result

Complexity compared

Approach	Time	Space
Naive Every subset, filter and deduplicate	O(n · 2ⁿ)	O(n) recursion plus the set
Optimal Sorted backtracking, skip duplicates	O(n · 2ⁿ) worst case, far less with pruning	O(n) recursion

Key takeaways

Sort + i > start skip + i + 1 recursion: the recipe for "each element once, no duplicate answers".

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem