Subset Sum Problem in O ( sum ) space | Java Program to get a subset with a with a sum provided by the user ; Returns true if there exists a subset with given sum in arr [ ] ; The value of subset [ i % 2 ] [ j ] will be true if there exists a subset of sum j in arr [ 0 , 1 , ... . , i - 1 ] ; A subset with sum 0 is always possible ; If there exists no element no sum is possible ; Driver code
public class Subset_sum { static boolean isSubsetSum ( int arr [ ] , int n , int sum ) { boolean subset [ ] [ ] = new boolean [ 2 ] [ sum + 1 ] ; for ( int i = 0 ; i <= n ; i ++ ) { for ( int j = 0 ; j <= sum ; j ++ ) { if ( j == 0 ) subset [ i % 2 ] [ j ] = true ; else if ( i == 0 ) subset [ i % 2 ] [ j ] = false ; else if ( arr [ i - 1 ] <= j ) subset [ i % 2 ] [ j ] = subset [ ( i + 1 ) % 2 ] [ j - arr [ i - 1 ] ] || subset [ ( i + 1 ) % 2 ] [ j ] ; else subset [ i % 2 ] [ j ] = subset [ ( i + 1 ) % 2 ] [ j ] ; } } return subset [ n % 2 ] [ sum ] ; } public static void main ( String args [ ] ) { int arr [ ] = { 1 , 2 , 5 } ; int sum = 7 ; int n = arr . length ; if ( isSubsetSum ( arr , n , sum ) == true ) System . out . println ( " There ▁ exists ▁ a ▁ subset ▁ with " + " given ▁ sum " ) ; else System . out . println ( " No ▁ subset ▁ exists ▁ with " + " given ▁ sum " ) ; } }