jain12

Subset sum problem by recursion

Jun 1st, 2020
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.53 KB | None | 0 0
  1. #include<iostream>
  2. using namespace std;
  3.  
  4. int IsSubsetSum(int arr[],int n,int sum){
  5.   if(sum==0)
  6.     return 1;
  7.   if(n==0&& sum!=0)
  8.     return 0;
  9.   if(arr[n-1]>sum)
  10.     return IsSubsetSum(arr,n-1,sum);
  11.   return IsSubsetSum(arr,n-1,sum-arr[n-1])|| IsSubsetSum(arr,n-1,sum);
  12.   }
  13.  
  14. int main(){
  15.     int arr[] = { 3, 34, 4, 12, 5, 2 };
  16.     int sum = 30;
  17.     int n = 6;
  18.     if (IsSubsetSum(arr,n,sum))
  19.         cout<<("Found a subset with given sum");
  20.     else
  21.         cout<<("No subset with given sum");
  22.     return 0;
  23.     }
Add Comment
Please, Sign In to add comment