We have discussed the “subset sum problem using dynamic programming” . We can solveĀ  subset sum problem using backtracking algorithm. For example if there is set S{ 1,3,9,2} and given sum is 5, find whether any subset of set S whose elements ads up to sum 5.

subset sum problem using backtracking

subset sum problem using backtracking

#include<iostream>
using namespace std;

int set[] = { 1, 3, 9, 2 };

void find (int pos, int sum, int tmpsum, int size, bool & found)
{
  if (sum == tmpsum)
    {
      found = true;
    }

  for (int i = pos; i < size; i++)
    {
          if (tmpsum + set[i] <= sum)
	    {
	      tmpsum += set[i];
	      find (i + 1, sum, tmpsum, size, found);
	      tmpsum -= set[i];
	    }
    }
}

int main ()
{
  // find array length
  int arr_size = sizeof (set) / sizeof (set[0]);

  // if given sum is 5
  int sum = 5;
  bool f = false;
  find (0, sum, 0, arr_size, f);

  if (f)
    cout << "YES" << endl;
  else
    cout << "NO" << endl;

  return 0;
}

 



Related Contents to follow