#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