-
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.