回溯算法(理论篇)

回溯法也可以叫做回溯搜索法，它是一种搜索的方式。回溯是递归的副产品，只要有递归就会有回溯。同时也也要知道溯法并不是什么高效的算法，它本质是穷举，然后筛选出符合条件的结果。如果想提高回溯的一些效率，可以加一些剪枝的操作(什么是剪枝呢?)

回溯算法解决的问题

• 组合问题：N个数里面按一定规则找出K个数的集合
  • 77.组合
  • 17.电话号码的字母组合
  • 39.组合总和
  • 40.组合总和II
  • 216.组合总和III
• 切割问题：一个字符串按一定的规则有几种切割方式
  • 131.分割回文串
  • 93.复原IP地址
• 子集问题：一个N个数的集合里面有多少符合条件的子集
  • 78.子集
  • 90.子集II
• 排列问题：N个数按照一定的规则全排列，有几种排列方式
  • 46.全排列
  • 47.全排列II
• 棋盘问题：N皇后，解数独
  • 51.N皇后
  • 37.解数独
• 其他问题
  • 491.递增子序列
  • 332.重新安排行程

其中，组合不强调元素的顺序，排列强调元素的顺序。例如:{1,2},{2,1}在组合时指一个集合，而在排列时指两个集合。换句话说，排列有序，组合无序。

回溯算法详解

回溯算法解决的问题，实质上就是一个决策树的遍历过程，需要思考3个问题：

1. 路径：也就是已经做出的选择
2. 选择列表：也就是当前可以做的选择
3. 结束条件：也就是达到决策树底层，无法再做选择的条件

回溯算法的框架：

List<List<?>> result = new ArrayList<List<?>>();
void backtrack(路径,选择列表){

	if (满足结束条件) { 
		result.add(路径); 
		return;
	}

    for(选择 in 选择列表){
        做选择;
        backtrack(路径,选择列表);
        撤销选择;
    }
}

回溯算法的核心：for循环里面的递归，再递归调用之前【做选择】，递归结束之后【撤销选择】，简单的说就是：

// 做选择
将该选择从选择列表中移除;
路径.add(选择);
backtrack(路径,选择列表);

// 撤销选择
路径.remove(选择);
将该选择再加入到选择列表;