Microsoft Interview Question

Given a dictionary and one string, create a valid sentence from the string by adding spaces in appropriate places. Difficult because you had to know to back track recursively