1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Aryabhata Apr 23 '13 at 5:06
  • $\begingroup$ Oh .. is this a homework? $\endgroup$ – AJed Apr 23 '13 at 12:36
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.