Subsequence Sum After Capping Elements
You are given an integer array nums of size n and a positive integer k.
An array capped by value x is obtained by replacing every element nums[i] with min(nums[i], x).
For each integer x from 1 to n, determine whether it is possible to choose a subsequence from the array capped by x such that the sum of the chosen elements is exactly k.
Return a 0-indexed boolean array answer of size n, where answer[i] is true if it is possible when using x = i + 1, and false otherwise.
Example 1
Input
nums = [4,3,2,4], k = 5Output
[false,false,true,true]For
x = 1 and x = 2, no subsequence of the capped array sums to 5, while for x = 3 and x = 4, subsequences [2, 3] and [3, 2] respectively sum to 5.Example 2
Input
nums = [1,2,3,4,5], k = 3Output
[true,true,true,true,true]For every value of
x, it is always possible to select a subsequence from the capped array that sums exactly to 3.Constraints
- 1 <= n == nums.length <= 4000
- 1 <= nums[i] <= n
- 1 <= k <= 4000