#include <iostream>
#include <iomanip>
using namespace std;

// knap1.cpp : rescursive solution to the exact sum knapsack problem
//
// beware: this isn't a knapsack problem at all as there are no values
// is greedy algorithm for maximizing space in a finite sample
//
int knapsack(int wts[], int n, int tw, int ci)
//  tw is the target wieght
	//  wts is a set of n weights
	//  ci is the index to start looking for a match at 
	//  returns 1 if there is a solution, 0 if not
{
	if (tw == 0) return 1;
	if (tw < 0 || ci == n) return 0;

	if (knapsack(wts, n, tw-wts[ci], ci+1)) {
			// we have an answer, so report it
			// this will print out the last number tried,
			// i.e. the number at a higher index in the array first
			cout << wts[ci] << ' ';
			return 1; // signal partial solution
		}
		else {
			// candidate won't work so try solving w/0 candidate
			return knapsack(wts,n,tw,ci+1);
		}
}

int main() {
	int wts[7] = { 2,2,2,5,5,9,11};
	if (knapsack(wts,7,18,0)) // target weight = 18 here
		cout << "solution found" << endl;
		else  cout << "no solution found " << endl;

}