面试算法题:爬楼梯，N级楼梯有多少种走法？

最近去面试时，在一家小公司面试时，公司小BOSS给我出了一道算法题：

一个人爬楼梯，一步可以迈一级，二级，三级台阶，如果楼梯有N级，要求编写程序，求总共有多少种走法。

这个问题应该是一个很老的题目了，用中学数学来说，就是一个**排列组合**问题。当时拿到这个题目之后，首先想到使用递归的思想去解决这个问题：

N级楼梯问题可以划分为：N-1级楼梯，N-2级楼梯，N-3级楼梯的走法之和。

先计算下0，1，2，3及楼梯有多少种走法：

那么，根据以上的分析很容易写出如下代码：

但是仅仅算出有多少种走法是很容易的，基于这个基础，如何输出具体的走法呢？

我们可以使用Stack数据结构和递归的思想去完成这个题目：

Stack用于保存每一步的走法。

具体代码如下所示：

* 一个人爬楼梯，一步可以迈一级，二级，三级台阶，如果楼梯有N级，编写程序，输出所有走法。