Combination Sum

NeetCode: Combination Sum · LeetCode: 39. Combination Sum · Difficulty: Medium

Given an array of distinct positive integers candidates and a target, return all unique combinations whose numbers sum to target. The same number may be used any number of times. Two combinations are different if the count of at least one number differs.

Example

Text

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

Brute force: try any number at every step, then dedupe

At each step try every candidate, subtracting it from the remaining target; stop when the remaining value hits 0 (record) or goes negative (dead end). Every combination is found once per ordering: [2, 2, 3], [2, 3, 2] and [3, 2, 2] are the same combination. Sorting each found combination and keeping it in a TreeSet removes the repeats, but the search does many times the necessary work. A TreeSet<List<Integer>> needs a comparator because List has no natural order, so the program supplies compare, which orders lists lexicographically. current.remove(current.size() - 1) removes by index, so it takes off the last element and does not look for a value.

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>> combinationSum(int[] candidates, int target) {
            Set<List<Integer>> found = new TreeSet<>(Main::compare);
            dfs(candidates, target, new ArrayList<>(), found);
            return new ArrayList<>(found);
        }

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

    // 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.combinationSum(new int[] {2, 3, 6, 7}, 7));
        System.out.println(sol.combinationSum(new int[] {2, 3, 5}, 8));
        System.out.println(sol.combinationSum(new int[] {2}, 1));
    }
}

Output

[[2, 2, 3], [7]]
[[2, 2, 2, 2], [2, 3, 3], [3, 5]]
[]

Time: roughly O(n^(T/m)) where T is the target and m the smallest candidate, since every permutation of every combination is explored. Space: O(T/m) recursion depth plus the stored results.

Optimal: start index plus sorted pruning

Remove the duplicates at the source by imposing an order. Once candidate i is chosen, only candidates at index i or later may follow, so a combination is built in exactly one order (2, 2, 3 but never 3, 2, 2). Passing i (not i + 1) to the recursive call allows reuse.

Sorting the candidates adds pruning: as soon as candidates[i] > remaining, every later candidate is too big as well, so break out of the loop.

Java

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

public class Main {
    static class Solution {
        public List<List<Integer>> combinationSum(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 (candidates[i] > remaining) {
                    break; // sorted, so all later ones are too large as well
                }
                current.add(candidates[i]);
                dfs(i, remaining - candidates[i], candidates, current, result); // i, not i + 1: reuse allowed
                current.remove(current.size() - 1);
            }
        }
    }

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

Output

[[2, 2, 3], [7]]
[[2, 2, 2, 2], [2, 3, 3], [3, 5]]
[]

Time: exponential in the worst case, bounded by O(n^(T/m)) nodes. Each combination is built exactly once and dead branches are cut immediately, so the search is far smaller in practice. Space: O(T/m) recursion depth plus the results.