Combination Sum IV
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.
Follow up: What if negative numbers are allowed in the given array? How does it change the problem? What limitation do we need to add to the question to allow negative numbers?
Example 1
Input
nums = [1,2,3], target = 4Output
7There are 7 possible ordered sequences that sum to 4, and different sequences are counted as different combinations.
Example 2
Input
nums = [9], target = 3Output
0The only number available is 9, which cannot be used to sum to 3.
Constraints
- 1 <= nums.length <= 200
- 1 <= nums[i] <= 1000
- All the elements of nums are unique.
- 1 <= target <= 1000
Asked at 6 companies
Practice questions like this out loud in a mock coding interview with a live AI interviewer. First one free.