377. Combination Sum IV

Question

Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target.

Algorithm

This question seems like a variant of combination sum. One can come up with a backtracking algorithm to build all possible combinations.

However, in this problem, we are not asked to build the combinations, but rather the total number of combinations, which is actually a simpler problem that can be solved with Dynamic Programming.

Initiation: dp[0] = 0;

State: (result) the number of combination to the target of I;

Transformation: dp[i] = dp[i - nums[j]];

Code

class Solution {
    public int combinationSum4(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int i = 1; i < dp.length; i++) {
            for (int j = 0; j < nums.length; j++) {
                if (i >= nums[j]) {
                    dp[i] += dp[i - nums[j]]; 
                }
            }
        }
        return dp[target];
    }
}