c++ - Backtrack in any programming language -

i given task of writing program string permutation. understand logic, not exact meaning of backtrack in program. please explain for-loop functionality, when swap called, when permutate() called, , 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    {         (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; } 

sketching call stack can understanding how algorithm works. example string "abc" starting point. basically, happen abc:

permute(abc, 0, 2)     = 0     j = 0     permute(abc, 1, 2)         = 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 example above, indentation defines happens inside each of recursive calls.

the reasoning behind loop every permutation of string abc given abc, bac , cba, plus every permutation of substrings bc, ac , ba (remove first letter each of previous ones). string s, possible permutations obtained swapping every position first one, plus of permutations of each of these strings. think of this: permuted string must start 1 of letters in original string, place every possible letter in first position, , recursively apply same method rest of string (without first letter).

that's loop doing: scan string current starting point (which i) end, , @ each step swap position starting point, recursively call permute() print every permutation of new string, , after restore string previous state, have original string repeat same process next position.

personally, don't comment saying "backtrack". better term "winding back", because @ point recursion winds , prepare string next recursive call. backtrack used situation in explored subtree , didn't find solution, go (backtrack) , try different branch. taken wikipedia:

backtracking general algorithm finding (or some) solutions computational problem, incrementally builds candidates solutions, , abandons each partial candidate c ("backtracks") determines c cannot possibly completed valid solution.

note algorithm not generate set of permutations, because can print same string more once when there repeated letters. extreme case when apply string "aaaaa", or other string 1 unique letter.