/* Solving existence and any solution variation of subset sum problem
 * Author: Xiaolan Zhang
 * Data: 10/10/2024
 */
#include <iostream>
#include <vector>

using namespace std;

/* Check whether there is a subset of numbers from X that add up to T
 @param: T sum to make
 @param: X a vector of values 
 @param: next: which value in X we are making decision on next 
 @return: true if one can make sum T using a subset from X[next...X.size()-1]
          false if otherwise
 */
bool subset_sum(int T, vector<int> X, int next){
    //base case
    if (T==0)
	    return true;
    else if (T<0)
	    return false;
    else if (next==X.size())
	    return false;
    else
    { //general case 
      //make the next decision: to include X[next] or not? 
      
      //try include it: then we want to see if we can make the smaller sum
      // using the rest of the values in X [next+1...]
      bool success = subset_sum(T - X[next], X, next+1);
      if (success) 
	      return true; //no need to explore the other option 
 
      //if not success, try the other option: exclude X[next]...
      success = subset_sum(T, X , next+1); //we commit to not include X[next],
					   //so try to make T using the rest of values in X

      return success;
    }
}

void PrintVector(vector<int> result)
{
	cout <<"     Result contains: ";
	    for (int i=0;i<result.size();i++)
		    cout <<result[i]<<" ";
	    cout <<endl;
}

/* Check whether there is a subset of numbers from X that add up to T
 * return one solution, and set succeed to true if found;
 * otherwise return empty vector and set succeed to false.
 @param: T sum to make
 @param: X a vector of values 
 @param: next: which value in X we are making decision on next 
 @param: succeed: set to true/false based upon whether it's possible or not 
 @return: vector storing subset that add up to T if found
          if not found, return empty vector
 */
vector<int> subset_sum(int T, vector<int> X, int next, bool & succeed){
    vector<int> result; //initialized to empty vector
	
    //helping with tracing 
    cout <<"subset_sum (T="<<T<<", next="<<next<<") called\n";
    cout <<"Press c and enter to continue:";
    char a;
    cin >> a;
    
    //base case
    if (T==0){
	    succeed = true;
    	    cout <<"subset_sum (T="<<T<<", next="<<next<<") return, success\n";
	    PrintVector (result);
	    return result;
    }
    else if (T<0){
	    succeed= false;
    	    cout <<"subset_sum (T="<<T<<", next="<<next<<") return, fail\n";
	    PrintVector (result);
	    return result;
    } else if (next==X.size()){
	    succeed= false;
    	    cout <<"subset_sum (T="<<T<<", next="<<next<<") return, fail\n";
	    PrintVector (result);
	    return result;
    }

    else 
    { //general case 
      //make the next decision: to include X[next] or not? 
      bool succeed1,succeed2;
      
      //try include it: then we want to see if we can make the smaller sum
      // using the rest of the values in X [next+1...]
      result  = subset_sum(T - X[next], X, next+1,succeed1);
      if (succeed1) {
	      //result stores a vector that adds up to T-X[next]
	      result.push_back (X[next]); //now values in result add up to T
	      succeed = true;
    	      cout <<"subset_sum (T="<<T<<", next="<<next<<") return, success\n";
	      PrintVector (result);
	      return result; //no need to explore the other option 
      }
 
      //if not success, try the other option: exclude X[next]...
      result = subset_sum(T, X , next+1, succeed2); //we commit to not include X[next],
					   //so try to make T using the rest of values in X
      if (succeed2) {
	      succeed = true;
    	      cout <<"subset_sum (T="<<T<<", next="<<next<<") return, success\n";
	      PrintVector (result);
	      return result; //values in result sum up to T
      } else {
      	succeed = false; 
	result.clear();
    	cout <<"subset_sum (T="<<T<<", next="<<next<<") return, fail\n";
	PrintVector (result);
      	return result; 
      }

    }
}

int main()
{
    //test case 
    vector<int> numbers = {7, 14, 15, 10};
    int sum = 29;
    
    /*
    cout <<"Entering a sum to make using values from 7, 14, 15, 10:\n";
    cin >>sum;
    if (subset_sum (sum, numbers, 0))
	    cout <<"we can make a sum of :"<<sum<<endl;
    else 
	    cout <<"we cannot make a sum of :"<<sum<<endl;
    */

    //test one solution 
    //Note: when testing recursive algorithm:
    //   first test the basecases, here, trye a negative sum, sum=0
    //   then test cases which has only one layer of recursion, e.g., 7, 5
    //   move to larger testcases from there
    cout <<"Entering a sum to make using values from 7, 14, 15, 10:\n";
    cin >>sum;
    bool succeed;
    vector<int> result = subset_sum (sum, numbers, 0, succeed);
    if (succeed){
	    cout <<"we can make a sum of :"<<sum<<endl;
	    cout <<"One way to do so is using: ";
	    for (int i=0;i<result.size();i++)
		    cout <<result[i]<<" ";
	    cout <<endl;
    }
    else 
	    cout <<"we cannot make a sum of :"<<sum<<endl;
    return 0;
}