I got thrown off by an interview question recently,
What structure do you use to find all the ways up a ladder with N steps in 1 or 2 steps moves?
It occured to me today that a graph expansion could be used but it's not optimal because when N = 30, it evalates almost 700,000 nodes on a single round of expansion.
Here's the output of solving for N = 5.
2 2 1 2 1 2 1 2 2 2 1 1 1 1 2 1 1 1 1 2 1 1 1 1 2 1 1 1 1 1
My instinct is that maybe this problem can be solved with regular methods from Discrete Math that I'm just not remembering.
Is there a way to get the set of sequences containing (1, 2) where the sum of the elements is N?
If anyone is interested here's the code of the program I wrote.