Dynamic Programming | A recursive solution for subset sum problem ; Returns true if there is a subset of set [ ] with sum equal to given sum ; Base Cases ; If last element is greater than sum , then ignore it ; else , check if sum can be obtained by any of the following ( a ) including the last element ( b ) excluding the last element ; Driver code
using System ; class GFG { static bool isSubsetSum ( int [ ] set , int n , int sum ) { if ( sum == 0 ) return true ; if ( n == 0 ) return false ; if ( set [ n - 1 ] > sum ) return isSubsetSum ( set , n - 1 , sum ) ; return isSubsetSum ( set , n - 1 , sum ) || isSubsetSum ( set , n - 1 , sum - set [ n - 1 ] ) ; } public static void Main ( ) { int [ ] set = { 3 , 34 , 4 , 12 , 5 , 2 } ; int sum = 9 ; int n = set . Length ; if ( isSubsetSum ( set , n , sum ) == true ) Console . WriteLine ( " Found ▁ a ▁ subset ▁ with ▁ given ▁ sum " ) ; else Console . WriteLine ( " No ▁ subset ▁ with ▁ given ▁ sum " ) ; } }