#ifndef BACKTRACK_H
    #define BACKTRACK_H
    //a is really not much use in most cases
    //k is the kth move.  Use it if you need to use the move later
    //input is the input data
    //ncandidates is the number of candidates returned at kth move
    //MAXCANDIDATES is the max possible candidate
    //finished is to indicate to continue search or quit.  One may use it to
    //stop when you have got a "solution".  Set it to "false" to run through
    //all possible solutions.
    void make_move(int a[],int k, void *input);
    void unmake_move(int a[], int k, void *input);
    void construct_candidates(int a[], int k, void *input,
                              int c[], int *ncandidates, int MAXCANDIDATES);
    bool is_a_solution(int a[],int k, void *input);
    void process_solution(int a[], int k, void *input, bool *finished);
    void backtrack(int a[], int k, void *input, int MAXCANDIDATES, bool *finished);
    #endif



    //backtrack.cc

    #include <cstdlib>
    #include <vector>
    #include <iostream>
    #include "backtrack.h"
    //a is the solution at this point
    //k don't worry!  The first call should be 0
    //input is the input data.  However you want to interpret it
    //MAXCANDIDATES is the max number of candidates at the  move
    //finished is to indicate to continue search or quit.  One may use it to
    //stop when you have got a "solution".  Set it to "false" to run through
    //all possible solutions.
    void backtrack(int a[], int k, void *input, int MAXCANDIDATES, bool *finished)
    {
      int *c=new int[MAXCANDIDATES]; // candidates for next position
      int ncandidates=0; // next position candidate count
      int i;
      if (is_a_solution(a,k,input))
        process_solution(a,k,input,finished);
      else{
        k = k+1;
        construct_candidates(a,k,input,c,&ncandidates,MAXCANDIDATES);
        for (i=0; i<ncandidates; i++) {
          a[k] = c[i];  //run through each candidate
          make_move(a,k,input);
          backtrack(a,k,input,MAXCANDIDATES, finished);
          if (*finished){
            delete []c;
            return; // terminate early
          }
          unmake_move(a,k,input);
        }
      }
      delete []c;
    }

    void make_move(int a[],int k, void *input)
    {

    }

    void unmake_move(int a[], int k, void *input)
    {

    }

    void construct_candidates(int a[], int k, void *input, int c[], int *ncandidates, int MAXCANDIDATES)
    {
            for(int i = 0; i < MAXCANDIDATES; i++)
            {
                    c[i] = i;
                    (*ncandidates)++;
            }
    }

    bool is_a_solution(int a[],int k, void *input)
    {
            unsigned i = k;
            std::vector<std::vector<int> > *datavector = static_cast<std::vector<std::vector<int> >* >(input);
            if(i == ((*datavector).size()-2))
                    return true;
            else
                    return false;
    }

    void process_solution(int a[], int k, void *input, bool *finished)
    {
            int sumweight = 0;
            int sumvalue = 0;
            std::vector<std::vector<int> > *datavector = static_cast<std::vector<std::vector<int> >* >(input);
            for(int i=0; i<k; i++)
            {
                    int obo = i+1;
                    sumweight += a[obo] * (*datavector)[i+1][0];
                    sumvalue += a[obo] * (*datavector)[i+1][1];
            }
            unsigned j = k+1;
            if(((sumweight <= (*datavector)[0][0]) && (sumvalue > (*datavector)[j][1])) || ((sumweight < (*datavector)[j][0]) && (sumvalue == (*datavector)[j][1])))
            {
                    (*datavector)[j][0] = sumweight;
                    (*datavector)[j][1] = sumvalue;
                    for(int z=1; z<k+1; z++)
                    {
                            (*datavector)[z][2] = a[z];
                    }
            }
    }