Subset Sum Problem in O ( sum ) space | C # 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
using System ; public class Subset_sum { static bool isSubsetSum ( int [ ] arr , int n , int sum ) { bool [ , ] subset = new bool [ 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 ( ) { int [ ] arr = { 1 , 2 , 5 } ; int sum = 7 ; int n = arr . Length ; if ( isSubsetSum ( arr , n , sum ) == true ) Console . WriteLine ( " There ▁ exists ▁ a ▁ subset ▁ with " + " given ▁ sum " ) ; else Console . WriteLine ( " No ▁ subset ▁ exists ▁ with " + " given ▁ sum " ) ; } }