You get an array nums of different positive integers and a positive integer target. Count the sequences of numbers taken from nums that add up to exactly target.
A number may be used as many times as you like. Order matters: 1, 3 and 3, 1 are different sequences and are counted separately.
The sequences are 1 + 1 + 1 + 1, 1 + 3 and 3 + 1.
2 + 5, 5 + 2, and the three orders of 2 + 2 + 3: 2 + 2 + 3, 2 + 3 + 2 and 3 + 2 + 2.
Every sum of fours and sixes is even, so 5 can't be reached.
Constraints
1 <= nums.length <= 2001 <= nums[i] <= 1000nums are all different.1 <= target <= 1000t from 1 to target, the number of sequences that add up to t is at most 2³¹ - 1. So the answer, and every count along the way, fits in a 32-bit signed integer.Think about the last number of a sequence that adds up to target. If it is x, what comes before it is any sequence adding up to target - x.
Look at the last number of a sequence that adds up to target. It is one of the numbers in nums, say x. Take it off, and what's left is a sequence adding up to target - x, any such sequence at all. So the sequences that end with x are exactly "a sequence for target - x, then x", and there are as many of them as there are sequences for target - x.
Time O(target · n)Space O(target)
The full walkthrough and code are part of Premium
3