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.length1)
{
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 hashset which will
make sure a character already used in an index does not come there again.
This code works for nonrepeated characters too.
void permute(char[] s, int i)
{
if (i==s.length1)
{
count++;
System.out.println(count + ") " + new String(s));
return;
}
HashSet<Character> charsDone =
new HashSet<Character> (); // <== initialize a hashset at each recursion level
int curr = i;
for (; i<s.length; i++)
{
if (charsDone.contains(s[i])) // <== if char is used, do not reprocess 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 nonrecursive 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
