Combination Sum IV

NeetCode: Combination Sum IV · LeetCode: 377. Combination Sum IV · Difficulty: Medium

Given an array of distinct positive integers nums and a target, return the number of sequences (order matters, numbers may be reused) whose sum is target. The answer is guaranteed to fit in a 32-bit integer.

Example

Text

Input:  nums = [1, 2, 3], target = 4    Output: 7
        (1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1)
Input:  nums = [9], target = 3          Output: 0

Brute force: plain recursion

Let count(t) be the number of sequences summing to t. The first number of a sequence can be any x <= t, after which the rest sums to t - x, so count(t) = sum of count(t - x) with count(0) = 1 (the empty sequence). Written directly, this recomputes every count(t') many times, which is exponential in target.

Only the final answer is guaranteed to fit in 32 bits. Intermediate counts for smaller targets may overflow, so the code relies on Java's int addition, which wraps around silently on overflow and never throws (Math.addExact would throw). Addition is correct modulo 2^32, and the true answer is below 2^31, so the wrapped result equals it.

Java

class Solution {
    private int count(int[] nums, int t) {
        if (t == 0) {
            return 1;
        }
        int total = 0;
        for (int x : nums) {
            if (x <= t) {
                total += count(nums, t - x); // wraps on overflow, no exception
            }
        }
        return total;
    }

    public int combinationSum4(int[] nums, int target) {
        return count(nums, target);
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.combinationSum4(new int[]{1, 2, 3}, 4));
        System.out.println(solution.combinationSum4(new int[]{9}, 3));
        System.out.println(solution.combinationSum4(new int[]{5}, 0));
    }
}

Output

7
0
1

Time: O(n^target) in the worst case (exponential). Space: O(target) recursion depth.

Better: memoization

There are only target + 1 distinct arguments to count. Cache each result when it is first computed. The cache is an Integer[], where null marks an empty slot. A sentinel such as -1 would be unsafe, because a wrapped intermediate count can be any int, including a negative one.

Java

class Solution {
    private int count(int[] nums, int t, Integer[] memo) {
        if (t == 0) {
            return 1;
        }
        if (memo[t] != null) {
            return memo[t];
        }
        int total = 0;
        for (int x : nums) {
            if (x <= t) {
                total += count(nums, t - x, memo);
            }
        }
        memo[t] = total;
        return total;
    }

    public int combinationSum4(int[] nums, int target) {
        Integer[] memo = new Integer[target + 1]; // null means "not computed yet"
        return count(nums, target, memo);
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.combinationSum4(new int[]{1, 2, 3}, 4));
        System.out.println(solution.combinationSum4(new int[]{9}, 3));
        System.out.println(solution.combinationSum4(new int[]{5}, 0));
    }
}

Output

7
0
1

Time: O(target * n). Space: O(target).

Optimal: bottom-up table

Fill dp[t] for t = 1..=target in increasing order; dp[t - x] is always ready. This has the same complexity as memoization but needs no recursion. The table is the minimal state, because dp[t] can depend on any earlier cell.

Loop order matters. Target on the outside and numbers on the inside counts each ordering separately, which is what this problem asks. Swapping the loops would count combinations, as in Coin Change II.

Java

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int t = 1; t <= target; t++) {
            for (int x : nums) {
                if (x <= t) {
                    dp[t] += dp[t - x];
                }
            }
        }
        return dp[target];
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.combinationSum4(new int[]{1, 2, 3}, 4));
        System.out.println(solution.combinationSum4(new int[]{9}, 3));
        System.out.println(solution.combinationSum4(new int[]{5}, 0));
    }
}

Output

7
0
1

Time: O(target * n). Space: O(target).