递归

递归是一个函数直接或间接地调用自身的过程

例如：递归实现 5！

深度优先搜索(DFS)

深度优先搜索 的主要思想是从起始节点开始，沿着一条路径尽可能深地探索，直到不能再前进，然后回溯到上一个未完全探索的节点，继续探索其他分支。可以把它想象成在一个迷宫中，一直沿着一条通道走，直到走到死胡同，然后返回上一个岔路口，选择另一条通道。如此搜索，直至找到目标状态，或者遍历完所有状态。所以，深度优先搜索也是一种“盲目”搜索。

深度优先搜索（Depth First Search，DFS），简称深搜，其状态“退回一步”的顺序符合“后进先出”的特点，所以采用“栈”存储状态。深搜可以采用直接递归的方法实现。

回溯法

回溯法也称为试探法，它是深度优先搜索的一种特殊形式。回溯的基本思想是：从问题的某一状态（初始状态）出发，搜索从这种状态出发所能达到的所有“状态”，当一条路走到“尽头”的时候（不能再前进），再后退一步或若干步，从另一种可能“状态”出发，继续搜索，直到所有的“路径”（状态）都试探过。

回溯是深搜的一种特殊应用或技巧，常用于解决组合优化问题，如排列、组合、子集生成等。

全排列

从 n 个不同元素中任取 m（m ≤ n）个元素，按照一定的顺序排列起来，叫做从 n 个不同元素中取出 m 个元素的一个排列。

例：n = 3；nums[1,2,3]；m = 2；

1,2 为 n 个元素 nums[1,2,3] 的一个排列；

1,3 为 n 个元素 nums[1,2,3] 的一个排列；

2,1 为 n 个元素 nums[1,2,3] 的一个排列...

当 m = n 时所有的排列情况叫全排列。

[1,2,3]、[1,3,2]、[2,1,3]、[2,3,1]、[3,1,2]、[3,2,1] 为 n 个元素 nums[1,2,3]的全排列。

深度优先搜索的模型

void dfs(int step)
{
	if(到目的地)
		输出解; // 判断边界,是否返回 
	else
		for(int i=1;i<=算符种数;i++)
		{
			if(满足条件)
			{
				保存结果;
				dfs(step+1); // 递归下一步
				恢复:保存结果之前的状态(回溯一步) 
			}
		}
}