K Sum Subset

Hard
0/120
Average time to solve is 45m
profile
Contributed by
13 upvotes
Asked in companies
ShareChatEPAM SystemsCodenation

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
4 16
1 3 5 9
6 10
3 34 4 12 5 2
Sample Output 1:
15
10
Explanation:
For the first test case, You 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.

For the second test case, you are given ‘arr’ = [3, 34, 4, 12, 5, 2], and ‘K’ = 10. We can take the subset of elements [3, 2, 5] which sums up to 10. Hence the answer is 10.
Sample Input 2:
2
5 1
10 2 18 4 5
1 10
5
Sample Output 2:
0
5
Hint

Try to find the sum of each subset.

Approaches (2)
Brute Force

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 currSum is not greater than K
      • Update maxSum by currSum
  • Finally, return maxSum
Time Complexity

O(N*(2^N)), Where N is the number of elements in the array.

 

We iterate through over all the subsets of the array that takes O(2^N) time. For each subset, we are also calculating the sum of the subset. Hence the overall time complexity is O(N*2^(N)).

Space Complexity

O(1).

 

No extra space is used in this algorithm. Hence the overall space complexity is O(1).

Code Solution
(100% EXP penalty)
K Sum Subset
Full screen
Console