Maximum size subset with given sum using Backtracking | Java Program to implement the above approach ; Initialise maximum possible length of subsequence ; Store elements to compare max_length with its size and change the value of max_length accordingly ; Store the elements of the longest subsequence ; Function to find the length of longest subsequence ; Update max_length ; Store the subsequence elements ; Recursively proceed with obtained sum ; poping elements from back of vector store ; if sum > 0 then we don 't  required thatsubsequence  so return and continue  with earlier elements ; Sort the given array ; Traverse the array ; If max_length is already greater than or equal than remaining length ; Driver code
import java . util . * ; class GFG { static int max_length = 0 ; static Vector < Integer > store = new Vector < Integer > ( ) ; static Vector < Integer > ans = new Vector < Integer > ( ) ; static void find_max_length ( int [ ] arr , int index , int sum , int k ) { sum = sum + arr [ index ] ; store . add ( arr [ index ] ) ; if ( sum == k ) { if ( max_length < store . size ( ) ) { max_length = store . size ( ) ; ans = store ; } } for ( int i = index + 1 ; i < arr . length ; i ++ ) { if ( sum + arr [ i ] <= k ) { find_max_length ( arr , i , sum , k ) ; store . remove ( store . size ( ) - 1 ) ; } else return ; } return ; } static int longestSubsequence ( int [ ] arr , int n , int k ) { Arrays . sort ( arr ) ; for ( int i = 0 ; i < n ; i ++ ) { if ( max_length >= n - i ) break ; store . clear ( ) ; find_max_length ( arr , i , 0 , k ) ; } return max_length ; } public static void main ( String [ ] args ) { int [ ] arr = { - 3 , 0 , 1 , 1 , 2 } ; int n = arr . length ; int k = 1 ; System . out . print ( longestSubsequence ( arr , n , k ) ) ; } }