回溯算法理论
- 回溯和递归式相辅相成的，只要有递归就会有回溯
- 一般 递归函数的下面就是 回溯的逻辑
- 回溯相当于穷举搜索的巧妙实现
- 回溯算法常解决的问题：
- 组合
- 切割
- 子集
- 排列
- 棋盘
- 回溯代码的框架
void backtracking(参数) { if (终止条件) { 存放结果; return; } for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) { 处理节点; backtracking(路径，选择列表); // 递归 回溯，撤销处理结果 } }
77.组合
题目链接:力扣
思路
首先应该先到的就是双层循环,,很难写，因为求的是组合，根据参数的不同，组合也不相同，无法用循环的方式覆盖所有可能，单纯的循环是行不通的
这道题的本质是对[1,n]中的数字进行 k 个数的穷举，就是要将所有满足条件的收集起来，此时就要想起来使用回溯算法，回溯算法的本质就是穷举
其实回溯算法就是通过递归控制有多少层for循环，递归里得每一层就是一个for循环
以求取 [1,2,3,4] 中所有可能出现的 2 个数的组合为例：
收集结果的集合nums在不断回溯
组合
class Solution { List<Integer> nums = new ArrayList<>(); List<List<Integer>> result = new ArrayList<>(); public List<List<Integer>> combine(int n, int k) { backtracking(n,k,1); return result; } void backtracking(int n,int k, int startIndex) { // 终止条件 if (nums.size() == k) { // 记录结果 result.add(new ArrayList(nums)); // 返回 return; } for (int i = startIndex; i <= n; i++) { nums.add(i); backtracking(n,k,i+1); nums.remove(nums.size()-1); } } }
回溯法的本质是穷举，对回溯唯一能做的优化就是剪枝，减去那些根本不需要的遍历，比如说这道题目的n = 4,k = 4
每递归一层，集合中的元素就添加一次，所以集合中有的元素个数就是nums.size()，还需要的元素数目是 k - nums.size()
所以在[1,n]中至多从该起始位置 n - (k - nums.size()） + 1 开始遍历
class Solution { List<Integer> nums = new ArrayList<>(); List<List<Integer>> result = new ArrayList<>(); public List<List<Integer>> combine(int n, int k) { backtracking(n,k,1); return result; } void backtracking(int n,int k, int startIndex) { // 终止条件 if (nums.size() == k) { // 记录结果 result.add(new ArrayList(nums)); // 返回 return; } for (int i = startIndex; i <= n - (k - nums.size()) + 1; i++) { nums.add(i); backtracking(n,k,i+1); nums.remove(nums.size()-1); } } }
