Make delicious recipes!

Backtracking

Backtracking is an algorithmic paradigm that tries different solutions until a working solution is found. Problems solved with backtracking usually can only be solved by trying every possible configuration and each configuration is tried only once. A naive solution for these problems is to try all configurations and output a configuration that works. Backtracking is an optimization over this naive approach and works in an incremental way.

Name ‘backtracking’ comes from the fact that we go back one level and remove the choice made at that level if that choice did not lead to a solution. Due to this, we do not needlessly continue exploring all the children configurations of this wrong choice and this is what improves the efficiency of backtracking over naive solution.



Print all permutations of a string (assume no duplicates)


Java code:

public class StringPermtations {

    static int count=0;
    public static void main(String[] args) 
    {
        String s = "abcdef";
        count=0; // counter to count the number of words formed
        permute (s.toCharArray(), 0);
    }

    static void permute(char[] s, int i) 
    {
        if (i==s.length-1)
        {
            count++; // count no of words output and print the permutation.
            System.out.println(count + ") " + new String(s));
            return;
        }
        int curr = i;
        for (; i<s.length; i++)
        {
            swap (s, i, curr);
            permute (s, curr+1);
            swap (s, i, curr);
        }
    }

    static void swap(char[] s, int i, int j) 
    {
        char c = s[i];
        s[i] = s[j];
        s[j] = c;
    }

}



Sample Run:
For input = "abcd", output is:

1) abcd
2) abdc
3) acbd
4) acdb
5) adcb
6) adbc
7) bacd
8) badc
9) bcad
10) bcda
11) bdca
12) bdac
13) cbad
14) cbda
15) cabd
16) cadb
17) cdab
18) cdba
19) dbca
20) dbac
21) dcba
22) dcab
23) dacb
24) dabc



Code to handle duplicate characters


To handle duplicate characters, we need to use a hash-set which will make sure a character already used in an index does not come there again.
This code works for non-repeated characters too.

void permute(char[] s, int i) 
{
    if (i==s.length-1)
    {
        count++;
        System.out.println(count + ") " + new String(s));
        return;
    }
    HashSet<Character> charsDone = 
        new HashSet<Character> (); //  <== initialize a hash-set at each recursion level
    int curr = i;
    for (; i<s.length; i++)
    {
        if (charsDone.contains(s[i])) //  <== if char is used, do not re-process it
            continue;
        charsDone.add(s[i]);
        swap (s, i, curr);
        permute (s, curr+1);
        swap (s, i, curr);
    }
}

void swap(char[] s, int i, int j) 
{
    char c = s[i];
    s[i] = s[j];
    s[j] = c;
}



Sample Run:
For input = "here", output is:
1) here
2) heer
3) hree
4) ehre
5) eher
6) erhe
7) ereh
8) eerh
9) eehr
10) rehe
11) reeh
12) rhee

Order of the above programs is O(n!)



Converting recursive to iterative programs


One of the most common tasks desired after implementing a recursive program is to convert it to a non-recursive program.
This is easy to do only when there is tail recursion* because in tail recursion, there is no need to save the point of return.
For other recursive programs, like the above, one not only needs to save the state of variables in a stack, but also the point of return which makes it complicated.

In the above problems, the recursion call is not a tail recursion and it is being called inside a loop.
So it cannot just be eliminated by a stack.

Look for "insertnode_recur" on StackOverflow for more.

*Tail recursion is one where recursive call is the last call in the function






Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal