64. Combination Sum IV

Medium · Dynamic Programming

Given an array of distinct positive integers and a target, count the number of ways to add up numbers from the array to reach exactly the target. Numbers may be reused, and different orderings count as different combinations (e.g. for [1,2], the target 3 can be made as 1+2 and 2+1 — two ways).

The input is [nums, target]. Return a single integer — the number of ordered combinations.

Examples

Example 1
Input: [[1,2,3],4]
Output: 7
Explanation: Seven ordered ways make 4: (1,1,1,1),(1,1,2),(1,2,1),(2,1,1),(2,2),(1,3),(3,1).
Example 2
Input: [[9],3]
Output: 0
Explanation: 9 cannot sum to 3, so the answer is 0.

Constraints