回溯算法 理论基础 回溯算法也叫做,回溯搜索法,它是一种搜索的方式
回溯的本质是穷举,穷举出所有的可能,再选出我们想要的答案
可以加一些剪枝的操作优化,但改变不了穷举的本质
回溯和递归是相辅相成的,递归函数的下面就是递归的过程
回溯算法解决的问题
组合问题:N个数里面按照一定规则找出k个数的集合
切割问题:一个字符串按照一定的规则,有几种切割方式
子集问题:一个N个数的集合里有多少符合条件的子集
排列问题:N个数按照一定规则全排列,有几种排列组合
棋盘问题:N皇后,解数独等
组合问题 :{1,2}{2,1}就是一个组合,不强调顺序
排列问题 :{1,2}{2,1}就是两个组合,有顺序
如何理解回溯法 回溯法解决的问题都可以抽象为树形结构 ,是的,我指的是所有回溯法的问题都可以抽象为树形结构!
因为回溯法解决的都是在集合中递归查找子集,集合的大小就构成了树的宽度,递归的深度,都构成的树的深度 。
递归就要有终止条件,所以必然是一棵高度有限的树(N叉树)。
这块可能初学者还不太理解,后面的回溯算法解决的所有题目中,我都会强调这一点并画图举相应的例子,现在有一个印象就行。
1 2 3 4 5 6 7 8 9 10 11 12 void backtracking(参数) { if (终止条件) { 存放结果; return; } for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) { 处理节点; backtracking(路径,选择列表); // 递归 回溯,撤销处理结果 } }
77.组合
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution { List<List<Integer>> ans = new ArrayList <>(); List<Integer> path = new ArrayList <>(); public List<List<Integer>> combine (int n, int k) { dfs(n, k, 1 ); return ans; } public void dfs (int n, int k, int start) { if (path.size() == k) { ans.add(new ArrayList <>(path)); return ; } for (int i = start; i <= n; i++) { path.add(i); dfs(n, k, i + 1 ); path.remove(path.size() - 1 ); } } }
77.组合优化
简单来说就是,数的每一层是dfs(),每一层的个数是for循环控制的
当n=4,k=4的时候,[1-4]中所有可能只有一种,所以要在for循环中,排除不需要的分支
1.已经选择的元素是path.size();
2.所需要的元素是k-path.size();
3.剩余元素为n-(k-size)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { List<List<Integer>> ans = new ArrayList <>(); List<Integer> path = new ArrayList <>(); public List<List<Integer>> combine (int n, int k) { dfs(n, k, 1 ); return ans; } public void dfs (int n, int k, int index) { if (path.size() == k) { ans.add(new ArrayList <>(path)); return ; } for (int i = index; i <= n - (k - path.size()) + 1 ; i++) { path.add(i); dfs(n, k, i + 1 ); path.removeLast(); } } }
216.组合优化III 在集合[1-9]中选取k个数,和n=4的组合
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class Solution { List<List<Integer>> ans = new ArrayList <>(); List<Integer> path = new ArrayList <>(); public List<List<Integer>> combinationSum3 (int k, int n) { dfs(k, n, 1 , 0 ); return ans; } public void dfs (int k, int n, int index, int sum) { if (sum > n) { return ; } if (path.size() > k) { return ; } if (path.size() == k && sum == n) { ans.add(new ArrayList <>(path)); return ; } for (int i = index; i <= 9 ; i++) { path.add(i); sum += i; dfs(k, n, i + 1 , sum); sum -= i; path.removeLast(); } } }