Search code examples
javaalgorithmrecursionpermutationbacktracking

Permutation of string using backtracking algorithm

I was reading the code below on Geeksforgeeks, but I just can't wrap my head around how it works! If anyone can explain it pictorially. That'd be great!

this is the code:

static void swap(char a[], int l, int r) {
    char temp = a[l];
    a[l] = a[r];
    a[r] = temp;
}

static void permute(char a[], int l, int r) {
    if (l == r)
        System.out.println(getString(a));
    else {
        for (int i = l; i <= r; i++) {
            swap(a, l, i);
            permute(a, l + 1, r);
            swap(a, l, i); // backtrack
        }
    }
}

enter image description here

Solution

  • I don't see where you're confused: you provided a picture that explains it quite clearly ... to me. :-)

    Termination condition (bottom row of your diagram, 2 red & 1 green items): if the list has only one remaining element to consider, there's nowhere to swap it. The permutation is done. return

    Otherwise ... For each item remaining in the array, swap that position into the left-most available spot. Move the "fixed" pointer one spot to the right, and call the routine on the rest of the array.

    Overall, this simply walks down the array: pick each item (in turn) for the first position; pick each remaining item (in turn) for the second; ... continue through the end of the list.

    Does that clear up anything for you?