Recursion IV: More Recursion Problems

This is a catch-up post, as I've been solving more recursion problems since the last post, but haven't had the chance to put them up on the blog. Since the last post, I started working on the problems from the book: Cracking The Coding Interview.

The book is written by Gayle Laakmann, an engineer at Google with a passion to train and mentor other people to become better computer scientists. He has plenty of experience interviewing at Google and other top companies, and in this book he shares his advice for most of the aspects of those sorts of interviews.

Major part of the book consists of interview questions, categorized by topic area, and the possible solutions. Recursion only comes in Chapter 8, but that's where I jumped first nonetheless, as this is my training focus right now.

Coin Change
The first problem I went on to solve involved calculating the number of ways N cents can be represented using quarters, dimes, nickels and pennies. This is my code:

      public static void getChange(int n, int[] coins, int sum){  
           if(sum == n)  
                System.out.println(coins[0] + "q," + coins[1] + "d," +   
                          coins[2] + "n," + coins[3] + "p");  
           else{  
                if(sum + 25 <= n){  
                     coins[0]++;  
                     getChange(n, coins, sum + 25);  
                     coins[0]--;  
                }  
                if(sum + 10 <= n){  
                     coins[1]++;  
                     getChange(n, coins, sum + 10);  
                     coins[1]--;  
                }  
                if(sum + 5 <= n){  
                     coins[2]++;  
                     getChange(n, coins, sum + 5);  
                     coins[2]--;  
                }  
                if(sum + 1 <= n){  
                     coins[3]++;  
                     getChange(n, coins, sum + 1);  
                     coins[3]--;  
                }  
           }  
      }  

The idea behind the code is relatively simple: build a recursion tree where each node branches off to 4 possibilities, while always making sure than proceeding to a certain branch will not take us over the given sum. Once we reach the desired sum, we are at a solution leaf, so print out the result.

Evaluation
One way I could improve the design of this code is by using some OO principles and wrap the Coins structure as an object and have the function return a list of such objects. I avoided that here for simplicity, as this is just proof of recursion concept.

There is a problem with this code in that it will return duplicate combinations of coins. The reason is because there is no differentiation between two pennies, two dimes, etc., so we can reach the same combination by taking different decisions at each recursion depth. For example, to represent 6 we can either select 6 pennies by going depth first on pennies branches, or we can select a nickel and a penny; however, selecting a penny and then a nickel will also be a possibility, which is impossible distinguish until we reach both of those leafs and notice the duplicate.

After reading the provided solution, I realized that I misread the question - it is asking for the number of ways, not the enumeration of all possibilities. The solution in the book also employs bottom-up recursion, as opposed to my top-down method.

It took me a while to understand the solution presented in the book. As we go deeper into the recursion tree, we solve the subproblem of making change for a smaller amount. So, when making change for 25, we look for ways to make change using 0 quarters, 0 dimes, 0 nickels first (i.e. using pennies). Then, we use 1 nickel, 2 nickels, etc., until we hit the sum limit. The base case of recursion is when we hit the lowest denominator - pennies, as we can always make up for remaining amount using pennies.

Balanced Parenthesis
The next problem I went on to solve was enumerating combinations of n-pairs of parenthesis. This one was fairly simple, and the my code closely matched the provided solution in the end:

      public List<String> generateParenthesis(int n){  
           List<String> list = new LinkedList<String>();  
           _generateParenthesis(0, 0, n, new String(), list);  
           return list;  
      }  
        
      private void _generateParenthesis(int open, int closed, int n, String s,   
                List<String> list){  
           if(closed == n)  
                list.add(s);  
           else{  
                if(open < n)  
                     _generateParenthesis(open + 1, closed, n, s + "(", list);  
                if(open > closed)  
                     _generateParenthesis(open, closed + 1, n, s + ")", list);  
           }  
      }  

We basically keep track of number of opened and closed parenthesis, opening parenthesis until we hit the provided limit and closing parenthesis while there are parenthesis to close (#open > #closed). Doing so recursively enumerates all possible combinations.

The only thing I noticed is that the book is missing one possibility for its provided example of 3 pairs: "(()())". The solution in the book also just prints out the solution at the base case, while I like to return the solution list as an object and use an "entry" method to recursion for a more user-friendly code design.

String Permutations
Finally, I worked on the interesting problem of string permutations. The problem definition is simple: given a string, output all possible permutations of its characters. I approached the solution this way:

      private static List<String> permuteString(String s){  
           List<String> list = new LinkedList<String>();  
           _permuteString(s, 0, list, new char[s.length()], new boolean[s.length()]);  
           return list;  
      }  
        
      private static void _permuteString(String s, int i, List<String> list, char[] p,   
                boolean[] used){  
           if(i == s.length()){  
                list.add(String.valueOf(p));  
           }  
           else{  
                for(int j = 0; j < s.length(); j++){  
                     if(used[j])  
                          continue;  
                     else{  
                          p[i] = s.charAt(j);  
                          used[j] = true;  
                          _permuteString(s, i+1, list, p, used);  
                          used[j] = false;  
                     }  
                }  
           }  
      }  

I approached this problem the same way as the number permutation problem. At each depth, I branch out to all possible characters from the string, but keep track of the characters I've already used (represented by the index at the original string and stored in the used[] array).

      public static List<String> permuteString(String s){  
           if(s.length() == 0){  
                return new LinkedList<String>(Arrays.asList(""));  
           }  
           else{  
                char first = s.charAt(0);  
                List<String> permutations = new LinkedList<String>();  
                for(String p : permuteString(s.substring(1)))  
                     combine(p, first, permutations);  
                return permutations;  
           }  
      }  
        
      private static void combine(String s, char c, List<String> combinations){  
           if(s.length() == 0)  
                combinations.add(String.valueOf(c));  
           else{  
                combinations.add(s + c);  
                combinations.add(c + s);  
                for(int i = 1; i < s.length(); i++)  
                     combinations.add(s.substring(0, i) + c + s.substring(i, s.length()));  
           }  
      }  

Here, at each deeper recursion level, we permute the substring of the original string, doing additional "merging" type operation as we go back up. E.g. when permuting "XYZ", we permute empty string first, then combine "Z" with the the empty string -> one way to do it: "Z", then we combine "Y" with permutation of "Z" -> two ways to do it: "YZ" or "ZY", then finally we combine "X" with permutations of "YZ" -> three ways to do it: "XYZ", "YXZ", "YZX", then three ways to do it with "ZY": "XZY", "ZXY" "ZYX", giving us all 6 combinations in the end.

This may seem like an intuitive and clever way to do it, but the top-down approach works better in this case. This is because even though the overall running time is bounded by O(n!), the combination part of top-down approach takes O(1) time, while doing the combination in bottom-up approach takes O(n).

I've ran the method for up to 10 characters, giving the following performance graph:

Note that the y-axis is logarithmic, and for the smaller input size, the top-down method is over an order of magnitude faster than the bottom-up approach. As we approach larger n, the asymptotic n! takes over, and the relative difference between the two method becomes marginal.