All possible ways of getting to a target sum

Suppose we are given infinite supply of {5,20,25} cents coins. What are the possible ways of get 1$?

We can solve above problem by backtracking algorithm as given below

   1:  private static void GetAllArrangements(int[] set, int index, int target, Dictionary<int, int> partialResult, List<List<int>> result)

   2:  {

   3:      for (int i = index; i < set.Length; i++)

   4:      {

   5:          int item = set[i];

   6:          int newTarget = target - item;

   7:          if (newTarget == 0)

   8:          {

   9:              if (!partialResult.ContainsKey(item))

  10:              {

  11:                  partialResult.Add(item, 1);

  12:              }

  13:              else

  14:              {

  15:                  partialResult[item]++;

  16:              }

  17:                      

  18:              List<int> newArrangement = new List<int>();

  19:              foreach (var item2 in set)

  20:              {

  21:                  int count = 0;

  22:                  partialResult.TryGetValue(item2, out count);

  23:                  newArrangement.Add(count);

  24:              }

  25:                      

  26:              result.Add(newArrangement);

  27:              partialResult[item]--;

  28:          }

  29:          else if (newTarget >= set[0])

  30:          {

  31:              if (!partialResult.ContainsKey(item))

  32:              {

  33:                  partialResult.Add(item, 1);

  34:              }

  35:              else

  36:              {

  37:                  partialResult[item]++;

  38:              }

  39:                      

  40:              GetAllArrangements(set, i, newTarget, partialResult, result);

  41:              partialResult[item]--;

  42:          }

  43:      }

  44:  }

All possible subsets of set with duplicates removed

Given a set of character {a, b, c, d} find all subsets. The final list should not have any duplicate entry.

   1:  /// <summary>

   2:  /// Given set {a, b, c, d} below are all subsets 

   3:  ///     d

   4:  ///     dc     c     

   5:  ///     dca    cb     b   a

   6:  ///     dcba   cba    ba

   7:  ///     dca    ca

   8:  ///     db

   9:  ///     dba

  10:  ///     da

  11:  ///  This algortithm picks an item from input set and prepends it with items present in output set as well as adds the item

  12:  ///  This guarantees unordered combinations. i.e. it treats "ab" and "ba" same ways.

  13:  /// </summary>

  14:  /// <param name="data"></param>

  15:  /// <returns></returns>

  16:  static List<string> GetAllSubsets(char[] data)

  17:  {

  18:      List<string> result = new List<string>();

  19:      for (int i = 0; i < data.Length; i++)

  20:      {

  21:          for (int j = result.Count - 1; j >= 0; j--)

  22:          {

  23:              StringBuilder sb = new StringBuilder(result[j]);

  24:              sb.Insert(0, data[i]);

  25:              result.Add(sb.ToString());

  26:          }

  27:          result.Add(new string(new char[] { data[i] }));

  28:      }

  29:   

  30:      return result;

  31:  }

Problem of arranging ill behaved children in a straight line

Your job is to arrange n ill-behaved children in a straight line, facing front. You are given a list of m statements of the form “i hates j”. If i hates j, then you do not want put i somewhere behind j, because then i is capable of throwing something at j.

Above problem can be solved by modeling above problem as direct graph where a directed edge exists between two children i and j if i hates j. Doing a Topological sort on this graph is going to give us the answer. Here is how Topological sort works:

1. Do a DFS on above graph.
2. Associate "finishing time" with each node while doing DFS.
3. Return the nodes in the decreasing order of "finishing time"

Iterative postorder traversal of Binary Tree Part-I

Iterative postorder traversal of Binary tree is tricky.  What makes it tricky is having to visit the same node multiple times and taking different actions on different visit. There are multiple ways of doing it. I have few of them coded in C# here.

Here is my node structure. Note I am using array to hold left and right pointers instead of Left and Right. Having children defined this way, reduces redundant code.

   1:  class Node

   2:  {

   3:      public int key;

   4:      public Node[] children = new Node[2];

   5:  }

I am going to use to Stack to keep track of nodes and associated visit count. The StackEntry is defined as follows

   1:  class StackEntry

   2:  {

   3:      public Node node;

   4:      public int visitcount;

   5:  }

Here is the code for PostOrder traversal of Binary Tree

   1:  public void PostOrder()

   2:  {

   3:      Stack<StackEntry> stack = new Stack<StackEntry>();

   4:      stack.Push(new StackEntry { node = root });

   5:      while (stack.Count > 0)

   6:      {

   7:          var top = stack.Peek();

   8:          if (top.visitcount < 2)

   9:          {

  10:              int direction = top.visitcount++;

  11:              if (top.node.children[direction] != null)

  12:              {

  13:                  stack.Push(new StackEntry { node = top.node.children[direction] });

  14:              }

  15:          }

  16:          else

  17:          {

  18:              stack.Pop();

  19:              Console.Write(" {0} ", top.node.key);

  20:          }

  21:      }

  22:  }

Above algorithm is doing following things:

1. Initially root is wrapped inside StackEntry and pushed onto the stack.
2. Inside while loop we look at stack's top element's visit count. 
3. If visitcount == 0, then we push top element's left child provided it is non-null and increment the visitcount.
4. If visitcount == 1, then we push top element's right child provided it is non-null and increment the visitcount.
5. If visitcount ==2, then we pop the element and print its value.

tryingout: tryingout: Recreating Binary Tree from Inorder and Postorder traversal data

tryingout: tryingout: Recreating Binary Tree from Inorder and Postorder traversal data

tryingout: Recreating Binary Tree from Inorder and Postorder traversal data

tryingout: Recreating Binary Tree from Inorder and Postorder traversal data

Recreating Binary Tree from Inorder and Postorder traversal data

This is continuation of earlier post about recreating Binary tree from given Preorder and Inorder data. This blog post has C# code from recreating the tree from inorder and postorder. The algo here is almost same as previous one except we start reading the postOrder data from right hand side as right most node is post-order transversal is Root node.

   1:  static Node DeserializeInorderPost(int[] inorder, int[] postorder)

   2:  {

   3:      int[] mapping = new int[inorder.Length];

   4:      for (int i = 0; i < inorder.Length; i++)

   5:      {

   6:          mapping[inorder[i]] = i;

   7:      }

   8:      int readPtr = inorder.Length -1;

   9:      return DeserializeInorderPost(inorder, postorder, mapping, 0, inorder.Length, ref readPtr);

  10:  }

  11:   

  12:  static Node DeserializeInorderPost(int[] inorder, int[] postorder, int[] mapping, int start, int end, ref int readPtr)

  13:  {

  14:      if (end == start)

  15:      {

  16:          return null;

  17:      }

  18:   

  19:      Node root = new Node { data = postorder[readPtr--] };

  20:      int divider = mapping[root.data];

  21:      root.right = DeserializeInorderPost(inorder, postorder, mapping, divider+1, end, ref readPtr);

  22:      root.left = DeserializeInorderPost(inorder, postorder, mapping, start, divider, ref readPtr);

  23:      return root;

  24:  }