Sum of subsets

Sum of subsets

Solution 01:  

A recursive solution for subset sum proble.

 #include<bits/stdc++.h>
using namespace std;

typedef long long ll;
map<int , int>M;

bool isSubsetsum(int set[], int n, int sum)
{
 // cout << "Enter-------"<<endl;
  if(sum == 0)return true;
  if(n == 0 && sum != 0)return false;

  ///If last element is greater than sum, then ignore it
  if(set[n-1] > sum)return isSubsetsum(set, n-1, sum);

  /// else, inluding last element || excluding last element

  return (isSubsetsum(set, n-1, sum) || isSubsetsum(set, n-1, sum - set[n-1]) );
}


int main()
{
    /* #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
  #endif*/

    //int set[] = {3,34, 4, 12, 5, 2};
    int set[12345];
    int sum = 9;
    //int n = sizeof(set)/sizeof(set[0]);
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
       cin >> set[i];
    }
    if(isSubsetsum(set, n, sum)){
      cout << "Found a subset with given sum";
    }
    else {
      cout << "No subset with given sum";
    }

    return 0;

}




Solution 02: DP

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
map<int , int>M;

bool isSubsetsum(int set[], int n, int sum)
{
 // cout << "Enter-------"<<endl;

  bool subset[n+1][sum+1];
  if(sum == 0)return true;

  /// If sum is 0, then answer is true
  for(int i = 0; i <= n; i++)subset[i][0] = true;

    /// If sum is not 0 and set is empty, then answer is false
    for(int i = 1; i <= sum; i++)subset[0][i] = false;

  ///Fill the subset table in bottom up manner
      for(int i = 1; i <= n; i++){
        for(int j = 1; j <= sum; j++){
          if(j < set[i-1])
            subset[i][j] = subset[i-1][j] || subset[i-1][j-set[i-1]];
        }
      }

      /// this code to print table
      /**for(int i = 0; i <= n; i++){
        for(int j = 0; j <= sum; j++)
        {
          printf("%4d",subset[i][j]);
        }
        printf("\n");
      }**/

      return subset[n][sum];
}


int main()
{
     #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
  #endif

    //int set[] = {3,34, 4, 12, 5, 2};
    int set[12345];
    int sum = 9;
    //int n = sizeof(set)/sizeof(set[0]);
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
       cin >> set[i];
    }
    if(isSubsetsum(set, n, sum)){
      cout << "Found a subset with given sum";
    }
    else {
      cout << "No subset with given sum";
    }

    return 0;

}

Share: