Combination Sum

Given an array of positive integers and a positive target, return all unique combinations of numbers that add up to target. A number may be used any number of times. Each combination is in non-descending order, and the list of combinations is sorted.

LeetCode: 39. Combination Sum

Example

Text

nums = [2, 3, 6, 7], target = 7  ->  [2, 2, 3], [7]
nums = [2, 3, 5],    target = 8  ->  [2, 2, 2, 2], [2, 3, 3], [3, 5]

Brute force: try every count of every number

A combination is fully described by how many times each distinct number is used. Number x can be used at most target / x times, so try every count for every number, and keep the choices whose sum is exactly target.

Java

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

public class Main {
    static void tryCounts(int[] nums, int i, int sum, int target, List<Integer> current, List<List<Integer>> out) {
        if (i == nums.length) {
            if (sum == target) out.add(new ArrayList<>(current));
            return;
        }
        int x = nums[i];
        for (int count = 0; count <= target / x; count++) {
            for (int c = 0; c < count; c++) current.add(x);
            tryCounts(nums, i + 1, sum + count * x, target, current, out);
            for (int c = 0; c < count; c++) current.remove(current.size() - 1);
        }
    }

    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());
    }

    static List<List<Integer>> combinationSum(int[] nums, int target) {
        int[] sorted = Arrays.stream(nums).distinct().sorted().toArray();
        List<List<Integer>> out = new ArrayList<>();
        tryCounts(sorted, 0, 0, target, new ArrayList<>(), out);
        out.sort(Main::compare);
        return out;
    }

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

Output

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

Time: O(∏ (target / xᵢ + 1)): every combination of counts is tried, including ones that overshoot the target early. Space: O(target / min) for the current combination, besides the output.

Optimal: sorted backtracking

Keep the remaining amount instead of checking the sum at the end. Choose numbers in non-descending order: after choosing nums[i], the next choice starts at i again (reuse allowed), never earlier (so [2, 3] and [3, 2] aren't both produced). Because the numbers are sorted, the loop can stop at the first number larger than what remains: every later number is larger too.

Java

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

public class Main {
    static void backtrack(int[] nums, int start, int remaining, List<Integer> current, List<List<Integer>> out) {
        if (remaining == 0) {
            out.add(new ArrayList<>(current)); // copy: current keeps changing
            return;
        }
        for (int i = start; i < nums.length; i++) {
            if (nums[i] > remaining) break; // sorted: nothing after this fits either
            current.add(nums[i]);
            backtrack(nums, i, remaining - nums[i], current, out);
            current.remove(current.size() - 1);
        }
    }

    static List<List<Integer>> combinationSum(int[] nums, int target) {
        int[] sorted = Arrays.stream(nums).distinct().sorted().toArray();
        List<List<Integer>> out = new ArrayList<>();
        backtrack(sorted, 0, target, new ArrayList<>(), out);
        return out;
    }

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

Output

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

Time: exponential in the worst case (the number of combinations itself can be exponential), but branches that can't reach the target are cut off immediately. Space: O(target / min) for the recursion, besides the output.

Sorting also makes the output sorted: combinations are produced in lexicographic order, so no final sort is needed.

Edge cases

No combination: an empty list.
Duplicate input values: removed with distinct() before sorting; otherwise the same combination would be produced once per copy.
Each number used at most once (LeetCode 40): recurse with i + 1 instead of i, and skip equal neighbours at the same depth.