## 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]; } }