Backtrack in any programming language [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

This question does not appear to be about programming within the scope defined in the help center.

Closed 8 years ago.

Improve this question

I was given a task of writing a program for string permutation. I understand the logic, but not the exact meaning of the Backtrack in this program. Please explain the for-loop functionality, when swap will be called, when permutate() will be called, and the exact meaning of backtrack.

# include <stdio.h>


void swap (char *x, char *y)
{
    char temp;
    temp = *x;
    *x = *y;
    *y = temp;
}


void permute(char *a, int i, int n) 
{
   int j; 
   if (i == n)
     printf("%s\n", a);
   else
   {
        for (j = i; j <= n; j++)
       {
          swap((a+i), (a+j));
          permute(a, i+1, n);
          swap((a+i), (a+j)); //backtrack
       }
   }
} 


int main()
{
   char a[] = "ABC";  
   permute(a, 0, 2);
   getchar();
   return 0;
}

Answer 1

Sketching the call stack can help you understanding how the algorithm works. The example string "ABC" is a good starting point. Basically, this is what will happen with ABC:

permute(ABC, 0, 2)
    i = 0
    j = 0
    permute(ABC, 1, 2)
        i = 1
        j = 1
        permute(ABC, 2, 2)
            print "ABC"
        j = 2
        string = ACB
        permute(ACB, 2, 2)
            print "ACB"
        string = ABC
    j = 1
    string = BAC
    permute(BAC, 1, 2)
        .... (everything starts over)

As usual, in the example above, indentation defines what happens inside each of the recursive calls.

The reasoning behind the for loop is that every permutation of string ABC is given by ABC, BAC and CBA, plus every permutation of the substrings BC, AC and BA (remove the first letter from each of the previous ones). For any string S, the possible permutations are obtained by swapping every position with the first one, plus all of the permutations of each of these strings. Think of it like this: any permuted string must start with one of the letters in the original string, so you place every possible letter in the first position, and recursively apply the same method to the rest of the string (without the first letter).

That's what the loop is doing: we scan the string from the current starting point (which is i) up to the end, and at each step we swap that position with the starting point, recursively call permute() to print every permutation of this new string, and after that we restore the string back to its previous state, so that we have the original string to repeat the same process with the next position.

Personally, I don't like that comment saying "backtrack". A better term would be "winding back", because at that point the recursion winds back and you prepare your string for the next recursive call. Backtrack is normally used for a situation in which you explored a subtree and you didn't find a solution, so you go back up (backtrack) and try a different branch. Taken from wikipedia:

Backtracking is a general algorithm for finding all (or some) solutions to some computational problem, that incrementally builds candidates to the solutions, and abandons each partial candidate c ("backtracks") as soon as it determines that c cannot possibly be completed to a valid solution.

Note that this algorithm does not generate the set of permutations, because it can print the same string more than once when there are repeated letters. An extreme case is when you apply it to the string "aaaaa", or any other string with one unique letter.

Answer 2

"Backtracking" means, you are gong back one step in your solution space (think of it as a decision tree and you are going up one level). It is usually used if you can rule out certain sub-trees in the decision space, and gives significant performance boost compared to full exploration of the decision tree if and only if it is very likely that you can rule out larger parts of the solution space.

You can find an exhaustive expalnation of a similar algorithm here: Using recursion and backtracking to generate all possible combinations