3685. Subsequence Sum After Capping Elements Medium

1/**
2 * [3685] Subsequence Sum After Capping Elements
3 *
4 * <p data-end="320" data-start="259">You are given an integer array nums of size n and a positive integer k.
5 * <p data-end="294" data-start="163">An array capped by value x is obtained by replacing every element nums[i] with min(nums[i], x).
6 * <p data-end="511" data-start="296">For each integer <code data-end="316" data-start="313">x from 1 to <code data-end="332" data-start="329">n, determine whether it is possible to choose a <span data-keyword="subsequence-array-nonempty">subsequence</span> from the array capped by x such that the sum of the chosen elements is exactly <code data-end="510" data-start="507">k.
7 * <p data-end="788" data-start="649">Return a 0-indexed boolean array <code data-end="680" data-start="672">answer of size <code data-end="694" data-start="691">n, where <code data-end="713" data-start="702">answer[i] is <code data-end="723" data-start="717">true if it is possible when using <code data-end="764" data-start="753">x = i + 1, and <code data-end="777" data-start="770">false otherwise.
8 *  
9 * <strong class="example">Example 1:
10 * <div class="example-block">
11 * Input: <span class="example-io">nums = [4,3,2,4], k = 5</span>
12 * Output: <span class="example-io">[false,false,true,true]</span>
13 * Explanation:
14 * 
15 * 	For x = 1, the capped array is [1, 1, 1, 1]. Possible sums are 1, 2, 3, 4, so it is impossible to form a sum of 5.
16 * 	For x = 2, the capped array is [2, 2, 2, 2]. Possible sums are 2, 4, 6, 8, so it is impossible to form a sum of 5.
17 * 	For x = 3, the capped array is [3, 3, 2, 3]. A subsequence [2, 3] sums to 5, so it is possible.
18 * 	For x = 4, the capped array is [4, 3, 2, 4]. A subsequence [3, 2] sums to 5, so it is possible.
19 * </div>
20 * <strong class="example">Example 2:
21 * <div class="example-block">
22 * Input: <span class="example-io">nums = [1,2,3,4,5], k = 3</span>
23 * Output: <span class="example-io">[true,true,true,true,true]</span>
24 * Explanation:
25 * For every value of x, it is always possible to select a subsequence from the capped array that sums exactly to 3.
26 * </div>
27 *  
28 * Constraints:
29 * 
30 * 	1 <= n == nums.length <= 4000
31 * 	1 <= nums[i] <= n
32 * 	1 <= k <= 4000
33 * 
34 */
35pub struct Solution {}
36
37// problem: https://leetcode.com/problems/subsequence-sum-after-capping-elements/
38// discuss: https://leetcode.com/problems/subsequence-sum-after-capping-elements/discuss/?currentPage=1&orderBy=most_votes&query=
39
40// submission codes start here
41
42impl Solution {
43    pub fn subsequence_sum_after_capping(nums: Vec<i32>, k: i32) -> Vec<bool> {
44        
45    }
46}
47
48// submission codes end
49
50#[cfg(test)]
51mod tests {
52    use super::*;
53
54    #[test]
55    fn test_3685() {
56    }
57}
58