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 moderate K; n up to ~40 with 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])

Expected approach

• Subset-sum DP over reachable sums: boolean dp[s] (bitset), answer = largest reachable s <= K; O(n*K) time. For small n with large values/K, meet-in-the-middle: enumerate both halves' subset sums, sort one half, binary-search the best partner — O(2^(n/2) log). Clarify positives-only vs negatives (with negatives, the greedy/bitset framing changes).