// Arup Guha
// 9/18/03
// Example of many-to-one reductions from subset sum to partition and
// from partition to subset sum.
// Note: We assume that the input set to both problems only has positive
//       integers.

#include <iostream.h>

bool subsetSum(int values[], int size, int target);
bool subsetSumHelp(int values[], int target, int size, int startindex);
int PartToSum(int values[], int size);
bool Partition(int values[], int size);
bool alternateSS(int values[], int target, int size);

void main() {

  int vals[10];
  vals[0] = 1; vals[1] = 3; vals[2] = 5; vals[3] = 10; vals[4] = 20;
  vals[5] = 40; vals[6] = 80; vals[7] = 160; vals[8] = 319;
  vals[9] = 640;

  if (Partition(vals, 10))
    cout << "Partition is successful.\n";
  else
    cout << "Partition can't be done.\n";  

  if (alternateSS(vals, 177, 10))
    cout << "Subset summing to 17 is found.\n";
  else
    cout << "Subset summing to 17 is NOT found.\n";

}

// Makes the initial call to the recursive method, indicating to
// look for the subset in the entire array.
bool subsetSum(int values[], int target, int size) {
  return subsetSumHelp(values, target, size, 0);
}

// Recursive method that determines whether or not a subset adding
// to target exists in the elements in the array values from 
// index startindex to the end of the array.
bool subsetSumHelp(int values[], int target, int size, int startindex) {

  // There are no elements in the set in question, must be false.
  if (startindex > size)
    return false;

  // The sum we are looking for is 0, a subset must exist (the empty set)
  if (target == 0)
    return true;
  
  // Recursively see what happens both when we put the current element
  // in the subset and when we do not.
  return (subsetSumHelp(values, target, size, startindex+1) || subsetSumHelp(values, target-values[startindex], size, startindex+1));
}

// Given a subset sum instance, this function returns a Partition instance
// that has a solution if and only if the subset sum instance does.
int* fReduc(int values[], int size, int target) {

  // Calculate the sum of the elements of values.
  int sum = 0;
  for (int i=0; i<size; i++)
    sum += values[i];

  // Subtract twice the amount of target from this value.
  int newval = sum - 2*target;

  // Create a new array newvals storing all the elements in values
  // plus the new element calculated above.
  int* newvals = new int[size+1];
  for (int i=0; i<size; i++)
    newvals[i] = values[i];
  newvals[size] = newval;

  // Return this array.
  return newvals;
}

// This function takes in an instance of the Partition problem and returns
// an instance of the Subset Sum problem that has a solution if and only
// if the Partition problem had a solution.
int PartToSum(int values[], int size) {

  // Sum up all the elements of values.
  int sum = 0;
  for (int i=0; i<size; i++)
    sum += values[i];

  // If the sum is odd, return an impossible target value.
  if (sum%2 == 1)
    return sum+1;

  // Otherwise return exactly half of the sum of the elements.
  else
    return sum/2;
  
}

// Solves Partition assuming a solution to Subset Sum.
// Shows a many-to-one mapping of Partition to Subset Sum.
bool Partition(int values[], int size) {

  return subsetSum(values, PartToSum(values,size), size);
}

// Solves Subset Sum problem assuming a solution to Partition.
// Shows a many-to-one mapping of Subset Sum to Partition.
bool alternateSS(int values[], int target, int size) {

  return Partition(fReduc(values,size,target), size+1);
}