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

Question

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:

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

Accepted Answer

Find the maximum sum of a subset of an array that does not exceed a given value K.

Sort the array in descending order to maximize the sum.
Iterate through the array and add elements to the sum until it exceeds K.
Return the sum obtained before exceeding K.