I only glanced at this, but usually when a recursive solution can be improved upon by dynamic programming, you can make a comparable improvement by memoizing in

I only glanced at this, but usually when a recursive solution can be improved upon by dynamic programming, you can make a comparable improvement by memoizing instead, without needing a full rewrite. In this case using stacks instead of recursion appears to have gotten in the way of that and might count as premature optimization. (I might be completely barking up the wrong tree as far as your particular code goes, again, but code described as generating all possible solutions could be made efficient without much change.) For example, the memoized word-splitting code at http://norvig.com/ngrams/ http://norvig.com/ngrams/ compared to the recent discussion here on HN of doing it with dynamic programming (as an interview problem).