The beauty of recursion

There are several programming models or techniques are powerful, yet simple and beautiful to solve problems. Recursion is one of them, others include dynamic programming, sliding windows, binary search.

Today I use recursion to solve two problems are permutation and combination of list of characters. For example, permutation of a, b, c are abc, acb, bac, bca, cab, cba. combinations are a, ab, abc, ac, b, bc, c.

Let's talk about permutation first, to generate them, image we have 3 balls in a bag with labels of a, b, c, we first one ball of 3 in the bag, then another ball out of 2 balls left, then last ball left in the bag. When there is no balls left in the bag, we are done, which is our recursion termination condition. So how we make sure we don't take the same ball twice in a permutation, we can mark it and unmark it once a permutation is generated. Here is the code:

	public static void permutationOf(char[] chars){
	permutationOfRec(chars, new char[chars.length], 0, new HashSet<Character>());
	}
	private static void permutationOfRec(char[] chars, char[] curr, int index, Set<Character> visited){
	int len = chars.length;
	if(len == index)
	System.out.println(curr);
	else{
	for(char c : chars){
	if(!visited.contains(c)){
	curr[index] = c;
	visited.add(c);
	permutationOfRec(chars, curr, index+1, visited);
	visited.remove(c);
	}
	}
	}
	}

view raw permuation.java hosted with ❤ by GitHub

Now let's talk about combination, which is a bit complicated than permutation. For the first position, we have possibilities of a, b, or c. And if we have a in the first position, we can have b or c; if we have b in the first position, we can only have c followed after; if we have c, nothing can follow. And every time we put a character in the string, we have one new combination. So we have
a
ab
abc
-->recursion terminated
remove c => ab
-->recursion terminated
remove c => a
ac
-->recursion terminated
remove c => a
-->recursion terminated
remove a=> ''
b
bc
c

Here is the code:

	public static void combinationOf(char[] chars){
	combinationOfRec(chars, 0, new StringBuilder());
	}
	private static void combinationOfRec(char[] chars, int index, StringBuilder sb){
	int len = chars.length;
	for(int i=index; i<len; i++){
	sb.append(chars[i]);
	System.out.println(sb);
	combinationOfRec(chars, i+1, sb);
	//once we finish all possible extensions we remove the last char
	//so we can start with new possiblities
	//e.g. we have ->a->ab->abc shorten to ab a
	// ac shorted to a ''
	//then we have ->b->bc shorted to b to ''
	//then we have ->c
	sb.setLength(sb.length()-1);
	}
	}

view raw combination.java hosted with ❤ by GitHub