3159 上台阶 V4 递归基础

小明的面前有一个n级的台阶，他每次可以上一级或是两级，现在他想知道每一种上台阶的方法，请你告诉他。

具体的，请你求出有多少种上台阶的方法；对于每一种上台阶的方法，请你用数字表示每一步的台阶数，并 将不同方法按字典序输出 。

例如，n=3，可行方法为111，12，21（3种），其中12表示第一步1个台阶，第二步2个台阶，因此按字典序输出：
3
111
12
21

输入格式

输入一个正整数n，表示台阶数量。

输出格式

第一行输出一个数m，表示上台阶的方法数。 之后m行每行输出一个由“1”、“2”组成的字符串，表示一种上台阶的方法。

输入样例

3

输出样例

3
111
12
21

数据范围

对于100%的数据，1<=n<=20；

今天懒，直接弄答案

#include<bits/stdc++.h>
using namespace std;
string paths[12000];
int cnt=0;
void Fib(int n,string path){
	if(n==0)
	paths[cnt++]=path;
	else if(n>0){
		Fib(n-1,path+"1");
		Fib(n-2,path+"2");
	}
}
int main(){
	int n;
	cin>>n;
	Fib(n,"");
	cout<<cnt<<endl;
	for(int i=0;i<cnt;i++)
		cout<<paths[i]<<endl;
 	return 0;
}