Thread: Backtracking algorithm??

Hi, I'm confused if it's possible to find exact one solution using backtrack algorithm?
Usually backtracking search the entire solution spaces.
I wonder if I can use it to find a feasible solution rather than search the entire solution space.

But I am stuck how to use when I should return from the recursive function stack?
Following is a backtracking algorithm to find the sum of array less < 13

Code:

using namespace std;
int array[] = { 8 , 15 , 2 , 3 };
bool choosen[4] = {0,0,0,0};
int best = 0;
int cw = 0;
int count(int idx) {
   return cw + array[idx-1];
}
void print() {
   for (int i = 0; i != 4; ++i) cout << (choosen[i] ? 1: 0);
   cout << endl;
}
void backtrack(int i) {
   if (i > 4) {
      if (cw > best) best = cw;
      print();
   }
   else {
      if (count(i) < 13) {
         cw = cw + array[i-1];
         choosen[i-1] = true;
         backtrack(i+1);
         cw = cw - array[i-1];
         choosen[i-1] = false;
      }
      backtrack(i+1);
   }
}
int main(void) {
   backtrack(1);
   cout << best << endl;
   return 0;
}

And the result is
1010
1001
1000
0100
0011
0010
0001
0000

11

I want to modify this to produce a solution of sum of array equation to 17
Which will produce one solution 0110 meaning that index[1] + index[2] == 17
Any advice is appreciated. Thx

Why not just modify it by adding an additional check that checks if it is the solution you are looking for? If that function returns true, return prematurely.