Subsequence With Max Sum Under K

Problem Given an array of integers and a value K, find the maximum sum of any subsequence whose sum does not exceed K.

Input / Output

• Input: int array nums, integer K.
• Output: the maximum achievable sum <= K.

Constraints

• Feasible sizes hinge on the approach: O(n*K) DP needs a moderate K; n up to ~40 with a huge K points to meet-in-the-middle.

Example

• nums = [1,2,3,4,5,6,7,16], K = 15 → 15 (e.g. [1,2,3,4,5])
• nums = [1,2,3,12,3], K = 10 → 9 ([1,2,3,3])