Combination Sum IV

Backpack VI (LI.564)

Given an integer array sizes with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example

I: sizes = [1,2,4], target = 4
O: [ [1,1,1,1], [1,1,2], [1,2,1], [2,1,1], [2,2], [4] ] = 6

State Graph

Code

public int backPackVI(int[] sizes, int target) {
    // create memo table
    int[] kp = new int[target + 1];
    // init base case
    kp[0] = 1;
    // topo order
    for (int s = 1; s <= target; s++) {
        for (int i = 0; i < sizes.length; i++) {
            if (sizes[i] <= s) {
                kp[s] += kp[s-sizes[i]];
            }
        }
    }
    // final answer
    return kp[target];
}

Better Code

public int backPackVI(int[] sizes, int target) {
    // create memo table
    int[] kp = new int[target + 1];
    // init base case
    kp[0] = 1;
    // sort so we can break
    Arrays.sort(sizes);
    // topo order
    for (int s = 1; s <= target; s++) {
        for (int i = 0; i < sizes.length; i++) {
            if (sizes[i] > s) {
                break;
            }
            kp[s] += kp[s-sizes[i]];
        }
    }
    // final answer
    return kp[target];
}

Combination Sum IV (LC.377)

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example

I: nums = [1,2,3], target = 4
O: [ [1,1,1,1], [1,1,2], [1,2,1], [1,3], [2,1,1], [2,2], [3,1] ] = 7

Analysis

Combination sum as the name suggests, we want combinations. This is a full knapsack problem.

Approach

1. Optimal subproblem
    cs[t] = maximum number of combinations to reach target t
2. Recurrence
    if nums[i] <= t: cs[t] += cs[t-nums[i]]
    else: cs[t] += 0
3. Topo Order
    for t from 1 to target
        for i from 0 to n-1
4. Base Case
    cs[0] = 1 b/c there's only one subset[] for target 0
5. Final Answer
    cs[target]

Code

public int combinationSum4(int[] nums, int target) {
    // create memo table
    int cs[] = new int[target + 1];
    // base case
    cs[0] = 1;
    // topo order
    for (int t = 1; t <= target; t++) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] <= t) {
                cs[t] += cs[t-nums[i]];
            }
        }
    }
    // final answer
    return cs[target];
}

Better Code

public int combinationSum4(int[] nums, int target) {
    // create memo table
    int cs[] = new int[target + 1];
    // base case
    cs[0] = 1;
    Arrays.sort(nums);
    // topo order
    for (int t = 1; t <= target; t++) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > t) {
                break;
            }
            cs[t] += cs[t-nums[i]];
        }
    }
    // final answer
    return cs[target];
}

Time & Space Complexity

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