#3685
Subsequence Sum After Capping Elements
medium · 25.1% accepted · 161 likes · top 4%
array · two pointers · dynamic programming · sorting
Description
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.
Solution