# Backtracking for listing k elements

Can someone give me a hand here, I am new to backtracking, and preparing for an interview. I couldn't even attempt this question, please help.

Describe a back tracking algorithm for efficiently listing all k-element subsets of n items.

For n = 5 the 3 element subsets are (1,2,3), (1,2,4), (1,2,5), (1,3,4), (1,3,5), (1,4,5), (2,3,4), (2,3,5), (2,4,5), (3,4,5)

In particular, I am interesting in first describing the solution vector representation to use, and then how I would partition the work among construct-candidates, is-a-solution and process-solution functions.

• The specific mention of is_a_solution, construct_candidates etc and your mention of talking to Skiena himself (on SO) now makes me wonder if you are just taking his current Spring 2013 course here: cs.sunysb.edu/~skiena/373. You can ask homework as long as you show some effort. (And if that is really not the case, I apologize, and hope that course page will be helpful to you). – Aryabhata Apr 23 '13 at 5:06
• Oh .. is this a homework? – AJed Apr 23 '13 at 12:36

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.