> I'd expect many candidates to think that you actually want them to generate all the permutations and then get bogged down in recursion. Ideally the candidate

> I'd expect many candidates to think that you actually want them to generate all the permutations and then get bogged down in recursion. Ideally the candidate should realize that this is computationally infeasible and quickly come up with a much more efficient solution, right? Perhaps they believe that this question filters out people who 1) don't have a feel for what is computationally feasible 2) will just dive into coding without spending 10 seconds to see if there's a significant optimization.