Combination Sum II

NeetCode: Combination Sum II · LeetCode: 40. Combination Sum II · Difficulty: Medium

Given an array candidates that may contain duplicates and a target, return all unique combinations that sum to target. Each element of candidates may be used at most once, and the result must not contain duplicate combinations.

Example

Text

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

Brute force: all subsets plus a set

Enumerate every subset with the include/skip tree from Subsets, keep the ones summing to target, sort each and insert it into a TreeSet to drop the duplicates that come from equal values at different positions (the two 1s in the first example). A TreeSet<List<Integer>> needs a comparator because List has no natural order, so the program supplies compare, which orders lists lexicographically. List.equals compares elements, so a plain HashSet would also drop duplicates, but its iteration order is unspecified. The solution returns List<List<Integer>>, LeetCode's return type, and current.remove(current.size() - 1) removes by index, which is the last element.

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

public class Main {
    static class Solution {
        public List<List<Integer>> combinationSum2(int[] candidates, int target) {
            Set<List<Integer>> found = new TreeSet<>(Main::compare);
            dfs(0, target, candidates, new ArrayList<>(), found);
            return new ArrayList<>(found);
        }

        private void dfs(int i, int remaining, int[] candidates, List<Integer> current, Set<List<Integer>> found) {
            if (i == candidates.length) {
                if (remaining == 0) {
                    List<Integer> combo = new ArrayList<>(current);
                    Collections.sort(combo);
                    found.add(combo);
                }
                return;
            }
            current.add(candidates[i]);
            dfs(i + 1, remaining - candidates[i], candidates, current, found);
            current.remove(current.size() - 1);
            dfs(i + 1, remaining, candidates, current, found);
        }
    }

    // Lexicographic order of two lists, used to keep the results in a fixed order.
    static int compare(List<Integer> a, List<Integer> b) {
        for (int i = 0; i < Math.min(a.size(), b.size()); i++) {
            int c = Integer.compare(a.get(i), b.get(i));
            if (c != 0) return c;
        }
        return Integer.compare(a.size(), b.size());
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.combinationSum2(new int[] {10, 1, 2, 7, 6, 1, 5}, 8));
        System.out.println(sol.combinationSum2(new int[] {2, 5, 2, 1, 2}, 5));
    }
}

Output

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

Time: O(n · 2^n). Space: O(n) recursion plus the stored combinations.

Optimal: sort, skip duplicates at the same level, prune

Sort a copy of the array so equal numbers sit next to each other. Each iteration of for (int i = start; i < n; i++) picks which number goes at the current position of the combination. If candidates[i] == candidates[i - 1] and i > start, that value was already tried at this position and every combination it could produce is already covered, so skip it. The i > start condition is required: using the second 1 after the first 1 was chosen at a shallower level is legal, and that is how [1, 1, 6] arises.

As in Combination Sum, break once a number exceeds the remaining target. Recurse with i + 1 because each element may be used only once.

Java

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

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

        private void dfs(int start, int remaining, int[] candidates, List<Integer> current, List<List<Integer>> result) {
            if (remaining == 0) {
                result.add(new ArrayList<>(current));
                return;
            }
            for (int i = start; i < candidates.length; i++) {
                if (i > start && candidates[i] == candidates[i - 1]) {
                    continue; // same value already tried at this position
                }
                if (candidates[i] > remaining) {
                    break;
                }
                current.add(candidates[i]);
                dfs(i + 1, remaining - candidates[i], candidates, current, result);
                current.remove(current.size() - 1);
            }
        }
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.combinationSum2(new int[] {10, 1, 2, 7, 6, 1, 5}, 8));
        System.out.println(sol.combinationSum2(new int[] {2, 5, 2, 1, 2}, 5));
    }
}

Output

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

Time: worst case O(n · 2^n) (the tree of choices); pruning and duplicate skipping reduce it, and no combination is generated twice. Space: O(n) recursion depth plus the results.