All problems

Combination Sum IV

Medium · dynamic programming

You are given a list nums of distinct positive integers and a positive integer target.

Build a sequence by choosing numbers from nums one after another. A number may be chosen as many times as you like. Count the sequences whose numbers add up to exactly target.

The order matters: 1, 3 and 3, 1 are two different sequences. Return how many sequences there are, or 0 if there are none.

Examples

Example 1

Input: nums = [1, 3], target = 4

Output: 3

The sequences are 1, 1, 1, 1 and 1, 3 and 3, 1.

Example 2

Input: nums = [2, 5], target = 3

Output: 0

Neither 2 nor 5 can be used to make exactly 3.

Example 3

Input: nums = [1, 2], target = 5

Output: 8

There are 8 ways: 1, 1, 1, 1, 1; four sequences with one 2 and three 1s; and three with two 2s and one 1.

Constraints

• 1 <= len(nums) <= 100
• 1 <= nums[i] <= 500, and all values are distinct.
• 1 <= target <= 500
• The answer, and the number of sequences for every smaller total, fit in a 32-bit signed integer.