- Arrays, Dynamic Programming, Greedy, Hash, Mathematical, subset

Largest value of K that a set of all possible subset-sum values of given Array contains numbers [0, K]

Given an array arr[] of N integers, the task is to find the maximum count of K, i.e, consecutive integers from 0 to K, that is present in the set S, where S contains all the possible subset-sum values of the array arr[].Examples:Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.  To complete your preparation from learning a language to DS Algo and many more,  please refer Complete Interview Preparation Course.In case you wish to attend live classes with experts, please refer DSA Live Classes for Working Professionals and Competitive Programming Live for Students.Input: arr[] = {1, 3}Output: 2Explanation: The possible subsets are {}, {1}, {3}, {1, 3} and there respective sums are {0, 1, 3, 4}. Therefore the maximum count of consecutive integers starting from 0 in the set containing all the subset sums is 2 (i.e, {0, 1}).Input: arr[] = {1, 1, 1, 4}Output: 8Explanation: The set containing all the subset sums of the given array is {0, 1, 2, 3, 4, 5, 6, 7}. Therefore the maximum count of consecutive integers starting from 0 is 8.Naive Approach: The given problem can be solved using Dynamic Programming by maintaining all the possible subset sums in an array which and be done using Knapsack Technique. Thereafter, calculating the maximum count of consecutive integers.Time Complexity: O(N*K) where K represents the sum of all elements in the array arr[].Auxiliary Space: O(K)Efficient Approach: The above problem can be solved using a Greedy Approach. Suppose the set containing all the subset sums of the array arr[] contains all integers in the range [0, X]. If a new number Y is introduced in the array, all integers in the range [Y, X + Y] will also be possible as the subset-sum. Using this observation, the given problem can be solved using the steps below: Sort the given array in non-decreasing order.Maintain a variable, say X as 0 which denotes that the integers in the range [0, X] are possible as the subset-sum of the given array arr[].In order to hold the continuity of consecutive integers, arr[i]