注册一亩三分地论坛,查看更多干货!
您需要 登录 才可以下载或查看附件。没有帐号?注册账号
x
本帖最后由 不知道小帅 于 2020-1-9 02:45 编辑
刚开始刷题的时候,backtrack对我特别tricky,我一直在想,这是些什么鬼东西,为什么加上,移除。
后来,慢慢参考了一些资料,也理解了其中的逻辑。原创不易,欢迎加米。
其实,要理解backtrack,首先必须理解recursion和dfs。
这里提一下。
这张图是树的dfs,或者说先序遍历(preorder traversal),上一个伪代码吧。
- private void dfs(TreeNode root) {
- if (root == null) return;
- visit(root);
- dfs(root.left);
- dfs(root.right);
- }
复制代码
visit就是一个函数,可以是加入数组,也可以是打印,这里我们不管。或者写一个多叉树的伪代码。
- def dfs(root):
- if root is None: return
- visit(root)
- for child in root.children:
- dfs(child)
复制代码
参考上图,红色点代表我们进入了这一个call stack,或者说开始调用dfs,作用在当前的node上面。
红色的×代表,当前调用结束,控制权返回上一层的recursion call。
下面写一个backtrack的模板:
- private void backtrack(int[] nums, List<Integer> track, List<List<Integer>> ans) {
- if (true) ans.add(new ArrayList<>(track); //base case
- else {
- for (int i: nums) {
- track.add(i); // choose
- backtrack(nums, track, ans); //explore (recursion call)
- track.remove(track.size() - 1); // unchoose
- }
- }
- }
复制代码
其实这个本质上就是dfs。继续参考上图,这个不过是在红色圆点的地方,执行了choose这个过程,也就是把结果加进track这个list。
然后remove的过程发生在红色×的地方,这个时候track里面的数字被移除,同时,控制权返回上一层recursion。
也就是说,track其实track的是你的call stack,因为backtracking的问题实质上是输出所有可能的路径。
base case指的就是你在叶节点的时候,大部分情况下base case会是track.size() == nums.length 之类的判断。
我们来看几道例题。
leetcode 46 permutations
我们先来看一下决策树。第一个红点处,我们的track加入1这个数字,第二个红点处,加入2, 第三个红点处,加入3。track = {1, 2, 3}
这时候,我们触发了base case 的条件,我们把第一个permutation加入了我们的ans list。然后第一个×的地方,我们执行remove操作,
这时候track只剩{1, 2}, 然后沿着这条线继续走,到了下一个×,这时候移除2。我们的track只剩{1}。然后经过后两个红点,得到{1, 3, 2}。
通过开始的base case,把这个结果加进我们的ans list里面。如此往复,直到函数结束。
因为backtrack的过程,choose explore unchoose 在代码上是挨着的,先执行choose,也就是在红点处执行,把这个结果加进track里面。
然后执行backtrack(explore),就看一下往哪走,然后是不是base case。之后执行unchoose,也就是在红色×的位置。此时这次调用执行完毕,
控制权移交上一层的recursion。
我们看一下代码。
- class Solution {
- public List<List<Integer>> permute(int[] nums) {
- List<List<Integer>> ans = new ArrayList<>();
- List<Integer> track = new ArrayList<>();
- backtrack(ans, track, nums);
- return ans;
- }
- private void backtrack(List<List<Integer>> ans, List<Integer> track, int[] nums) {
- if (track.size() == nums.length){
- ans.add(new ArrayList<>(track));
- }
- else {
- for (int i = 0;i < nums.length;++i){
- if (track.contains(nums)) {
- continue;
- }
- track.add(nums);
- backtrack(ans, track, nums);
- track.remove(track.size() - 1);
- }
- }
- }
- }
复制代码
这个代码其实有可以优化的地方,但是这里我们只讲思想。优化是后来的事情。
这个算法的时间复杂度首先要看有多少个节点,最底下一层有n!个叶节点,总共n层,也就是节点总数不超过n*n!。
因为在每一个节点都有一次track.contains,这是线性扫描。所以,复杂度是n。最终总的复杂度是O(n^2 * n!)。有优化的空间,
但是不论如何优化,不会低于n!的时间复杂度。
因为暴力枚举所有情况,其实复杂度还是很爆炸的。
我们再来看一道例题。
leetcode 78 Subsets
这个题目其实有两种决策树。
还是以[1, 2, 3]为例子。
第一种办法我觉得比较直观。
这个方法就是说,第一层加不加1,第二层加不加2,第三层加不加3. 直到最后我们初始的list为空。
比较直观。我们来贴一下代码。
- class Solution {
- public List<List<Integer>> subsets(int[] nums) {
- List<List<Integer>> ans = new ArrayList<>();
- List<Integer> track = new ArrayList<>();
- List<Integer> numslist = new ArrayList<>();
- for (int i: nums) numslist.add(i);
- backtrack(ans, track, numslist);
- return ans;
-
- }
-
- private void backtrack(List<List<Integer>> ans, List<Integer> track, List<Integer> nums) {
- if (nums.isEmpty()) ans.add(new ArrayList<>(track));
- else {
- int n = nums.remove(nums.size() - 1);
- //left branch
- //choose since choose empty, implicitly choose
- backtrack(ans, track, nums);
- //since choose empty, no need to remove
-
- //right branch
- track.add(n);
- backtrack(ans, track, nums);
- nums.add(n); // when unchoose, we need to restore the original list
- track.remove(track.size() - 1);
- }
- }
- }
复制代码
base case就是num这个list为空的时候。这个代码和图片有一点点不符合,应该3是在第一层。因为对list来说,removelast的复杂度是常数级别,
但是remove头部就是线性的。但是思想是一样的。
这种做法的时间复杂度,每个节点其实是O(1)的,所以就看多少个节点,叶子节点总共2^n个,因为是完全二叉树,总节点数量应该是2*2^n,
所以复杂度是O(2*2^n),也就是O(2^n)。指数级别。
方法二
我们引入了start index防止重复,start从上一层到下一层一定是递增的。需要注意的是,这个时候我们没有base case的判定了。我们会把所有节点(包括根节点)
一起加入我们的answer list里面去。下面是代码。
- class Solution {
- public List<List<Integer>> subsets(int[] nums) {
- List<List<Integer>> ans = new ArrayList<>();
- List<Integer> track = new ArrayList<>();
- backtrack(ans, track, nums, 0);
- return ans;
-
- }
-
- private void backtrack(List<List<Integer>> ans, List<Integer> track, int[] nums, int start) {
- ans.add(new ArrayList<Integer>(track));
- for (int i = start; i < nums.length; ++i) {
- track.add(nums);
- backtrack(ans, track, nums, i + 1);
- track.remove(track.size() - 1);
- }
- }
- }
复制代码
这个代码更短,但是对我来说,更难想到一些。复杂度是所有的节点数量,也就是O(2^n)。对比上一个解法,有常数项的优势。
leetcode 113 Path Sum 2
直接贴代码,这里其实if 和 else重叠的地方可以放在外面,但是为了更好的符合模板,或者更好想到一些。
base case,然后主体是 choose explore unchoose。
- class Solution {
- public List<List<Integer>> pathSum(TreeNode root, int sum) {
- List<Integer> track = new ArrayList<>();
- List<List<Integer>> ans = new ArrayList<>();
- backtrack(root, sum, track, ans);
- return ans;
- }
-
- private void backtrack(TreeNode root, int sum, List<Integer> track, List<List<Integer>> ans) {
- if (root == null) return;
- if (root.left == null && root.right == null && root.val == sum) {
- track.add(root.val);
- ans.add(new ArrayList<>(track));
- track.remove(track.size() - 1);
- }
- else {
- track.add(root.val);
- backtrack(root.left, sum - root.val, track, ans);
- backtrack(root.right, sum - root.val, track, ans);
- track.remove(track.size() - 1);
- }
- }
- }
复制代码
时间复杂度就是节点的总数,因为每个节点只过一遍。O(n)
leetcode 51 N- Queens
有了上面几个题目的积累,这个题目其实就迎刃而解了。主要是需要多一些剪枝和判定的过程。
我们就是每一列,每个点去放置queen,看看是否可行。如果可行就继续,不可行就剪枝。
所以终止条件(base case)就是col == n的时候。
- class Solution {
- public List<List<String>> solveNQueens(int n) {
- List<List<String>> ans = new ArrayList<>();
- List<String> track = new ArrayList<>();
- char[][] board = new char[n][n];
- for (int i = 0; i < n; ++i) {
- for (int j = 0; j < n; ++j) {
- board[j] = '.';
- }
- }
- backtrack(n, board, ans, 0);
- return ans;
- }
-
- private void backtrack(int n, char[][] board, List<List<String>> ans, int col) {
- if (col == n) ans.add(construct(board));
- else {
- for (int row = 0; row < n; ++row) {
- if (isSafe(board, row, col)) {
- board[row][col] = 'Q'; // choose
- backtrack(n, board, ans, col + 1); //explore
- board[row][col] = '.'; // unchoose
- }
- }
- }
-
- }
- private boolean isSafe(char[][] board, int row, int col) {
- for (int i = col - 1; i >= 0; --i) {
- if (board[row] == 'Q') return false;
- if (row + col - i < board.length && board[row + col - i] == 'Q')
- return false;
- if (row - col + i >= 0 && board[row - col + i] == 'Q')
- return false;
- }
- return true;
- }
-
-
-
- private List<String> construct(char[][] board) {
- List<String> track = new ArrayList<>();
- for (int i = 0; i < board.length; ++i) {
- track.add(new String(board));
- }
- return track;
- }
- }
复制代码
这个时间复杂度如果没有剪枝直接到最后一层的话有n^n个叶节点,总共节点数量是n^n + n^(n-1) + n^ (n -2) + ..+ n,等比数列求和。不会超过2*n^n,也就是O(n^n)
而且每一步判定是否安全也是O(n)的时间复杂度。最坏最坏就是O(n*n^n) 即O(n^(n+1)),当然实际上还是比这好得多。这里每一层的意思就是每一列,每个分支的意思就是从第0行开始放置。
原创不易,欢迎加米。为了造福新人,就不设置隐藏了。总结:
backtrack心中一定要有“树”,然后知道每一层的意义是什么,每一个分支又是什么意义。然后套用模板,从做题的角度来看,可以解决大部分问题。
楼主刷题时间不多,代码可能写得不是那么好,主要是思路要表达到位。如果讲得不清楚的地方,或者讲得不好的地方欢迎指正和讨论。
补充内容 (2020-1-9 06:22):
对于Subsets的时间复杂度有一点异议,“ans.add(new ArrayList<Integer>(track));” 应该是线性时间的操作,在worst case中,每一次backtrack都需要执行一次,所以总体的TC应该是O(N * 2^N). 这里之前没有想到。
补充内容 (2020-1-9 06:22):
还有就是,不知道为什么代码中间有些地方nums[i]的[i]被吞掉了。。。
补充内容 (2020-1-9 09:08):
主要的参考资料是两个人的视频,第一个是一个印度小哥 Ravindrababu Ravula, youtube上有。他讲的recursion。
第二个是Marty Stepp的CS106B的lec 9 - 11, B站有存档。
补充内容 (2020-1-9 22:20):
发现很多人收藏。很高兴可以分享自己看法,但是花很久码字,还是希望打赏大米。如果大家觉得讲得清楚的话,也会考虑出其他类型的讲解。 |