Practice/Meta/Leetcode 377. Combination Sum IV

Leetcode 377. Combination Sum IV

CodingOptional

Problem

Given an array of distinct positive integers nums and a target integer target, return the total count of different ordered sequences that sum exactly to target. You may use each number from nums as many times as needed.

Important: The order of numbers in a sequence matters. For example, [1, 2] and [2, 1] are considered two different sequences.

Requirements

1. Count all possible ordered sequences where elements sum to target
2. Numbers from nums can be reused unlimited times
3. Different orderings of the same numbers count as separate sequences
4. All numbers in nums are distinct and positive
5. Return the total count as an integer

Constraints

• 1 ≤ nums.length ≤ 200
• 1 ≤ nums[i] ≤ 1000
• All elements of nums are unique
• 0 ≤ target ≤ 1000
• The answer is guaranteed to fit in a 32-bit integer

Examples

Example 1:

Input: nums = [1, 2, 3], target = 4 Output: 7 Explanation: The possible sequences are: [1, 1, 1, 1] [1, 1, 2] [1, 2, 1] [2, 1, 1] [2, 2] [1, 3] [3, 1]

Example 2:

Input: nums = [9], target = 3 Output: 0 Explanation: There is no way to sum to 3 using only the number 9

Example 3:

Input: nums = [1, 2, 5], target = 5 Output: 9 Explanation: The possible sequences include: [1, 1, 1, 1, 1], [1, 1, 1, 2], [1, 1, 2, 1], [1, 2, 1, 1], [2, 1, 1, 1], [1, 2, 2], [2, 1, 2], [2, 2, 1], [5]