K Sum Subset Problem Statement

You are provided with an array arr of size N and an integer K. Your objective is to compute the maximum sum of a subset of the array such that this sum does not exceed K.

Example:

Input:

arr = [1, 3, 5, 9], K = 16

Output:

15

Explanation:

A possible subset is [9, 5, 1] which sums to 15, hence the result is 15.

Constraints:

• 1 <= T <= 10
• 1 <= N <= 40
• 0 <= K <= 10^9
• 0 <= arr[i] <= 10^9

Time Limit: 1 second