Last Updated: 13 Oct, 2021
K Sum Subset
Hard
Asked in companies
You are given an array ‘arr’ of size ‘N’ and an integer ‘K’. Your task is to find the maximum subset-sum of the array that is not greater than ‘K’.
For Example:
Your are given ‘arr’ = [1, 3, 5, 9], and ‘K’ = 16, we can take the subset of elements [9, 5 ,1] which sums up to 15. Hence the answer is 15.
Input Format:
The first line of input contains a single integer ‘T’ representing the number of test cases.
The first line of each test case contains two space-separated integers, ‘N’ and ‘K’, denoting the number of elements and the given integer.
The second line of each test case contains ‘N’ space-separated integers representing the elements of the array.
Output Format:
For each test case, print a single integer representing the maximum subset-sum not greater than ‘K.’
Print a separate line for each test case.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N <= 40
0 <= K <= 10^9
0 <= arr[i] <= 10^9
Time Limit: 1 sec
Approaches
In this approach, we will iterate over all the possible subsets of the given array, and then we will find the maximum sum subset whose sum is not greater than K.
The total number of subsets of an array is 2^N or 1 << N in the bitshift operator.
Algorithm:
- Set N as the size of the arr
- Iterate i from 0 to 1 << N
- Set currSum as 0
- Iterate j from 0 to N
- If i AND (1 << j) is not 0
- Add arr[j] to currSum
- If i AND (1 << j) is not 0
- If currSum is not greater than K
- Update maxSum by currSum
- Finally, return maxSum
In this approach, we will use the meet in the middle search technique, and it is only used when the input is small enough. It divides the array into two sub-arrays, then solves them individually and merges the arrays.
After creating both sub-arrays, we will traverse through one subarray and find the remaining sum in the other subarray. We will do the binary search in the other subarray to find the remaining sum. In the end, we will obtain the maximum subset-sum not greater than K.
Algorithm:
- Create two sets firstHalf and secondHalf
- Find all the subset sums in firstHalf and secondHalf, and store their values in the arrays subsetSumA, subsetSumB
- Sort the array subsetSumB
- Traverse all the values in subsetSumA, where subsetSumA[i] is less than K
- Binary search largest position where value is less than K - subsetSumA[i] on the array subsetSumB, and set it as pos
- If the pos is equal to the size fo subsetSumB
- Then decrease the pos by 1
- Update maxValue with subsetSumA[i] + subsetSumB[pos]
- Return the maxValue