Unfortunately, backtracking is not taught in many universities although it is a basic technique in algorithms and programming. You can backtrack using two methods: recursive or iterative. In the iterative, you use a stack. In the recursive version, you use the built-in memory stack by calling functions recursively.
A code that generates something similar to what you want is the following (it is left as an exercise to do exactly what you want.).
void backtrack(vector<int> v, int index, int max, int n) {
1) v.push_back(index);
2) if (v.size() == n) { print(&v); }
else {
3) for (int i = index + 1; i <= max; i++) {
4) backtrack(v, i, max, n);
}
}
}
This is called from the main function as: backtrack(v, 1, 5, 3); where v is a vector, and 1 is the initial element to be inserted in the vector.
You can implement your print as following:
void print(vector<int>* v) {
printf("( ");
for (int i = 0; i < v->size(); i++) {
printf("%d ", v->at(i));
if (i < v->size() - 1) { printf(", "); }
}
printf(") \n");
}
Note that the output of the program above is: (1,2,3), (1,2,4), (1,2,5), (1,3,4), (1,3,5), (1,4,5). -- Try to correct it. [Hint: use a for-loop in main]. Usually, a backtrack function has a a helper function (e.g. backtrack_helper). I haven't used a helper in here. But you can use it in your improved version.
Remark:
I added some comments in the backtrack version to show how I got this backtracking. In 1) I did the action that is supposed to be taken. In 2) I check whether I have reached a correct solution . In our case, a correct solution is when we have a vector of size n (3). If I dont reach the correct solution, I go to backtrack more. The for-loop is the most important thing in the program. I check the last element to be inserted in the vector (call it index). Then in the for-loop I call backtrack for all the neighbors of this element. These neighbors are the elements that can be inserted after index. These are called sometimes legal neighbors of index. -- It may sound weird a bet now. Let me know if you need more clarifications.
