Largest Time for Given Digits

More deceiving than it looks: https://leetcode.com/problems/largest-time-for-given-digits/description/

Given an array of 4 digits, return the largest 24 hour time that can be made.

The smallest 24 hour time is 00:00, and the largest is 23:59.  Starting from 00:00, a time is larger if more time has elapsed since midnight.

Return the answer as a string of length 5.  If no valid time can be made, return an empty string.

Example 1:

Input: [1,2,3,4]
Output: "23:41"

Example 2:

Input: [5,5,5,5]
Output: ""

One way is to use backtracking, here is the gist of it:

• First sort the array in descending order. This will guarantee that the first solution found is the optimal
• Backtrack it
• For each index from 0..3, you'll need to use different rules based on the time structure. For example, for position 0, it is only allowed to have digits 2..0. And so on
• As you backtrack, if you find a solution return
• Given the small size of the input (4), even the exponential should do it (think about 4^4, or 2^8, that's 256....)

Code is down below, cheers, Marcelo.

public class Solution
{
 public string LargestTimeFromDigits(int[] A)
 {
  Array.Sort(A);
  int[] nums = new int[A.Length];
  for (int i = 0; i < nums.Length; i++) nums[i] = A[A.Length - i - 1];
  Hashtable used = new Hashtable();
  string retVal = "";

  if (LargestTimeFromDigits(nums, 0, used, "", ref retVal)) return retVal;
  return "";
 }

 private bool LargestTimeFromDigits(int[] nums,
          int currentIndex,
          Hashtable used,
          string current,
          ref string retVal)
 {
  if (currentIndex >= nums.Length)
  {
   retVal = current;
   return true;
  }

  switch (currentIndex)
  {
   case 0:
    for (int i = 0; i < nums.Length; i++)
    {
     if (!used.ContainsKey(i) && nums[i] >= 0 && nums[i] <= 2)
     {
      used.Add(i, true);
      if (LargestTimeFromDigits(nums, currentIndex + 1, used, current + nums[i].ToString(), ref retVal)) return true;
      used.Remove(i); 
     }
    }
    break;
   case 1:
    for (int i = 0; i < nums.Length; i++)
    {
     if (!used.ContainsKey(i))
     {
      if (current.StartsWith("2"))
      {
       if (nums[i] >= 0 && nums[i] <= 3)
       {
        used.Add(i, true);
        if (LargestTimeFromDigits(nums, currentIndex + 1, used, current + nums[i].ToString() + ":", ref retVal)) return true;
        used.Remove(i);
       }
      }
      else
      {
       used.Add(i, true);
       if (LargestTimeFromDigits(nums, currentIndex + 1, used, current + nums[i].ToString() + ":", ref retVal)) return true;
       used.Remove(i);
      }
     }
    }
    break;
   case 2:
    for (int i = 0; i < nums.Length; i++)
    {
     if (!used.ContainsKey(i) && nums[i] >= 0 && nums[i] <= 5)
     {
      used.Add(i, true);
      if (LargestTimeFromDigits(nums, currentIndex + 1, used, current + nums[i].ToString(), ref retVal)) return true;
      used.Remove(i);
     }
    }
    break;
   case 3:
    for (int i = 0; i < nums.Length; i++)
    {
     if (!used.ContainsKey(i))
     {
      used.Add(i, true);
      if (LargestTimeFromDigits(nums, currentIndex + 1, used, current + nums[i].ToString(), ref retVal)) return true;
      used.Remove(i);
     }
    }
    break;
  }

  return false;
 }
}