DFS深度优先搜索

1.跳台阶一共有n级，每次走一级或者两级，问一共有多少种方案

分析，如果台阶为1，只有一种走法，如果台阶为2，可以走一次二或者两次1，有两种结果。

2.递归实现指数型枚举。从1-n中随机选取任意多个整数，输出所有的可能方案。

所有方案数为2的n次方。从1-n依次考虑每个数选/不选。

递归/DFS最重要的是顺序，做到补充不漏。

分析：从第一个元素也就是1开始，依次向后确认每一位的值存在或者不存在，所以才在主程序中使用dfs(1)。在dfs函数中，进行每一位元素的判断并输出，试用嵌套方式。

3.递归实现排列型枚举。按照字典序输出1-n所有不重复的序列，要求每一行不允许出现重复的数字。

strcmp 字典序：看ASCII码值大小。

思路：依次枚举每个位置可以放哪些数字，有几种可能。这道题和前一道题的不同之处在于出现过的数字不允许再次出现，所有这里额外设置一个数字用来标记出现过的数字。

实现回溯部分需要再度理解。数组st标识该数是否出现过，返回类型为bool，出现过后存入输出数组arr中，下一步进行递归调用，对后一个位置的数据进行相同的步骤，在左侧全部遍历完成后回溯到上一层，修改数据改为没有进入过，核心与深度优先搜索完全符合，先把一个位置的数据可能全部搜索完毕后回溯到上一层，再次进行遍历。

4.递归实现组合型枚举。排列组合。输入两个自然数，从n个数中任取r个数字，输出所有的组合，所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，每个元素占三个字符的位置，所有的组合也按字典顺序。

思路：排列需要考虑顺序，组合不需要考虑顺序。思路还是和上一题一样，依次枚举每个位置放哪个数。

要求数据按顺序输出，所以如果第一位是最大的数字的话，需要直接进行剪枝操作。其余两个位置类似。

5.P1036洛谷

思路：理解剪枝。(（x-1）+（n-start+1）)<k return ;