Password Cracker

Problem is described here: https://www.hackerrank.com/challenges/password-cracker. First, this is in the recursion section of the page - that should give you a hint that a recursive solution might be your best bet.
The problem can be solved by:
 - Determining whether the attempt password starts with one of the passwords
 - If so, remove it from the attempt password, call it recursively
 - Keep track of the passwords used
 - The moment that the attempt password is empty, you have found a solution
 - If none is found, well, none is found

My first attempt kind of worked, but timed out on few cases:

When looking at the test cases that timed out, one stood out:

a aa aaa aaaa aaaaa aaaaaa aaaaaaa aaaaaaaa aaaaaaaaa aaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab

Now if you notice it, it is clear that the attempt password will never have a solution given that there is one character in the attempt password that is not present in any of the passwords. Adding this small check to the code was enough to make it pass all through. Code is below, cheers!!! Marcelo.

using System; using System.Collections.Generic; using System.IO; using System.Collections; class Solution { static void Main(String[] args) { int t = Int32.Parse(Console.ReadLine()); string[] solution = new string[t]; for (int i = 0; i < t; i++) { int n = Int32.Parse(Console.ReadLine()); string[] words = Console.ReadLine().Split(' '); string attempt = Console.ReadLine(); string[] wordsInPass = new string[3000]; for (int j = 0; j < wordsInPass.Length; j++) wordsInPass[j] = ""; Hashtable mark = new Hashtable(); foreach (string w in words) { foreach (char c in w) { if (!mark.ContainsKey(c)) mark.Add(c, true); } } bool found = true; foreach (char c in attempt) { if (!mark.ContainsKey(c)) { found = false; break; } } if (!found) { solution[i] = "WRONG PASSWORD"; } else { if (Process(attempt, words, n, wordsInPass, 0)) { solution[i] = ""; foreach (string s in wordsInPass) { if (s.Length > 0) { solution[i] += s + " "; } } } else { solution[i] = "WRONG PASSWORD"; } } } for (int i = 0; i < t; i++) { Console.WriteLine(solution[i]); } } static bool Process(string attempt, string[] words, int n, string[] wordsInPass, int currentIndex) { if (attempt.Length == 0) { return true; } for (int i = 0; i < n; i++) { if (attempt.StartsWith(words[i])) { wordsInPass[currentIndex] = words[i]; if (Process(attempt.Substring(words[i].Length), words, n, wordsInPass, currentIndex + 1)) { return true; } wordsInPass[currentIndex] = ""; } } return false; } }