Loading problem…
Given an array of **distinct** integers `nums` and a target integer `target`, return the number of possible combinations that add up to `target`. The test cases are generated so that the answer can fit in a **32-bit** integer. **Note:** Different sequences are counted as different combinations (i.e., order matters).
Example 1
Input: nums = [1,2,3], target = 4
Output: 7
Explanation: Order matters, so these 7 sequences all count: (1,1,1,1), (1,1,2), (1,2,1), (2,1,1), (2,2), (1,3) and (3,1).
Example 2
Input: nums = [9], target = 3
Output: 0
Explanation: The only number, 9, is already larger than the target 3, so no sequence adds up to 3.
Example 3
Input: nums = [1,2,3], target = 32
Output: 181997601
Explanation: Each sequence ends in 1, 2 or 3, so ways(t) = ways(t-1) + ways(t-2) + ways(t-3), with ways(0) = 1. The values grow as 1, 1, 2, 4, 7, 13, … and reach 181997601 at t = 32.
Because order matters, this is really counting ordered sequences. Let dp[t] be the number of ordered ways to make t. Any such sequence ends in some num x, and removing it leaves an ordered way to make t-x — so dp[t] = sum over x of dp[t-x].
Run checks all cases above. Submit evaluates all test cases.