前言 回溯是我的薄弱点，所以写点杀卡尔的题目
首先来看杀卡写的模板吧，有一说一还挺有用
void backtracking(参数) { if (终止条件) { 存放结果; return; } for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) { 处理节点; backtracking(路径，选择列表); // 递归 回溯，撤销处理结果 } }
这个还是简单的，但我还是没剪枝！
class Solution { //组合问题呢，就得有starindex了，因为不能重复啊 ArrayList<Integer>path=new ArrayList<>(); List<List<Integer>>res=new ArrayList<>(); public List<List<Integer>> combine(int n, int k) { back(n, k, 1); return res; } void back(int n,int k,int starIndex) { if(path.size()==k) { res.add(new ArrayList<>(path)); return; } for(int i=starIndex;i<=n;i++) { path.add(i); back(n, k, i+1); path.remove(path.size()-1); } } }
剪枝：
class Solution { //组合问题呢，就得有starindex了，因为不能重复啊 ArrayList<Integer>path=new ArrayList<>(); List<List<Integer>>res=new ArrayList<>(); public List<List<Integer>> combine(int n, int k) { back(n, k, 1); return res; } void back(int n,int k,int starIndex) { if(path.size()==k) { res.add(new ArrayList<>(path)); return; } for(int i=starIndex;i<=n-(k-path.size())+1;i++)//就是这里变了， { path.add(i); back(n, k, i+1); path.remove(path.size()-1); } } }
我一开始的误区是什么
我一开始写成了
void back(String digits,String[]numString,int starIndex,int num) { if(num==digits.length()) { list.add(temp.toString()); return; } for(int i=starIndex;i<numString[i].length();i++) { temp.append(numString[num].charAt(i)); back(digits, numString, , num); } }
我想的是,”ab”,”cd”，然后每个里面也需要去重，
但是其实是不需要的，因为你ac,ae,agxxxxx都是算的，所以不需要starindex
正解：
class Solution { List<String> list = new ArrayList<>(); StringBuilder temp = new StringBuilder(); public List<String> letterCombinations(String digits) { if (digits == null || digits.length() == 0) { return list; } String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};//建立一个一一对应关系 back(digits, numString, 0); return list; } //一个组合问题，这边不用starIndx，因为你ad,ag,aj都算的啊 void back(String digits,String[]numString,int num) { if(num==digits.length()) { list.add(temp.toString()); return; } String str=numString[digits.charAt(num)-'0']; for(int i=0;i<str.length();i++) { temp.append(str.charAt(i)); back(digits, numString, num+1); temp.deleteCharAt(temp.length()-1); } } }
自己写居然一遍过，太屌了
class Solution { ArrayList<Integer>path=new ArrayList<>(); List<List<Integer>>res=new ArrayList<>(); public List<List<Integer>> combinationSum(int[] candidates, int target) { back(candidates, target, 0,0); return res; } //有一说一这个里面隐藏了剪枝问题,写到了再说 //然后可以重复选取，那么就可以从0开始 void back(int []candidates,int target,int sum,int startIndex)//sum是当前和 { //返回条件 if(sum>target) { return; } else if(sum==target) { res.add(new ArrayList<>(path)); return; } for(int i=startIndex;i<candidates.length;i++) { sum+=candidates[i]; path.add(candidates[i]); back(candidates, target, sum,i); sum-=candidates[i]; path.remove(path.size()-1); } } }
但我知道是可以剪枝的，如何剪枝呢
class Solution { public List<List<Integer>> combinationSum(int[] candidates, int target) { List<List<Integer>> res = new ArrayList<>(); Arrays.sort(candidates); // 先进行排序 backtracking(res, new ArrayList<>(), candidates, target, 0, 0); return res; } public void backtracking(List<List<Integer>> res, List<Integer> path, int[] candidates, int target, int sum, int idx) { // 找到了数字和为 target 的组合 if (sum == target) { res.add(new ArrayList<>(path)); return; } for (int i = idx; i < candidates.length; i++) { // 如果 sum + candidates[i] > target 就终止遍历 if (sum + candidates[i] > target) break; path.add(candidates[i]); backtracking(res, path, candidates, target, sum + candidates[i], i); path.remove(path.size() - 1); // 回溯，移除路径 path 最后一个元素 } } }
如果大于了就直接终止遍历，注意这样得先排序
这个去重已经是套路了
class Solution { ArrayList<Integer>path=new ArrayList<>(); List<List<Integer>>res=new ArrayList<>(); int sum=0; boolean[]isvisited; public List<List<Integer>> combinationSum2(int[] candidates, int target) { Arrays.sort(candidates); isvisited=new boolean[candidates.length]; back(candidates, target, 0); return res; } void back(int []candidates,int target,int startIndex) { if(sum==target) { res.add(new ArrayList<>(path)); return; } for(int i=startIndex;i<candidates.length;i++) { if(sum+candidates[i]>target) { break; } if(i>0&&candidates[i]==candidates[i-1]&&!isvisited[i-1]) { continue; } isvisited[i]=true; sum+=candidates[i]; path.add(candidates[i]); back(candidates, target, i+1); isvisited[i]=false; sum-=candidates[i]; path.remove(path.size()-1); } } }
我一开始的误区是，没有看清题，没看到是要分割，还以为是找到所有的回文字符串
然后分割的具体，是startIndex作为第一刀，i作为第二刀，这个思路要会
class Solution { List<List<String>> lists = new ArrayList<>(); Deque<String> deque = new LinkedList<>(); public List<List<String>> partition(String s) { back(s, 0); return lists; } private boolean isPalindrome(String s, int startIndex, int end) { for (int i = startIndex, j = end; i < j; i++, j--) { if (s.charAt(i) != s.charAt(j)) { return false; } } return true; } void back(String s ,int startIndex)//以starx开始分割，i作为分割的右边界 { if(startIndex>=s.length()) { lists.add(new ArrayList<>(deque)); return; } for(int i=startIndex;i<s.length();i++) { if(isPalindrome(s, startIndex, i)) { String str=s.substring(startIndex,i+1); deque.add(str); }else { continue; } back(s, i+1); deque.removeLast(); } } }
这题比较简单，注意了，为什么add刀res的操作不在if里面呢
因为我们本来就是要无条件的把所有的情况全加进去，所以直接add就行了
class Solution { //子集问题，这个就比较简单了，只要记得starIndex就行了 ArrayList<Integer>path=new ArrayList<>(); List<List<Integer>>res=new ArrayList<>(); public List<List<Integer>> subsets(int[] nums) { back(nums, 0); return res; } void back(int []nums,int starIndex) { res.add(new ArrayList<>(path)); if(starIndex>=nums.length) { return; } for(int i=starIndex;i<nums.length;i++) { path.add(nums[i]); back(nums, i+1); path.remove(path.size()-1); } } }
也是去重问题，和组合总和II一个套路
class Solution { ArrayList<Integer>path=new ArrayList<>(); List<List<Integer>>res=new ArrayList<>(); boolean []isused; public List<List<Integer>> subsetsWithDup(int[] nums) { isused=new boolean[nums.length]; Arrays.sort(nums); back(nums, 0); return res; } void back(int []nums,int starIndex) { res.add(new ArrayList<>(path));//但是这里也是一样的，子集问题存所有的情况，所以先add就行了 if(starIndex>=nums.length) { return; } for(int i=starIndex;i<nums.length;i++) { if(i>0&&nums[i]==nums[i-1]&&!isused[i-1]) { continue; } path.add(nums[i]); isused[i]=true; back(nums, i+1); path.remove(path.size()-1); isused[i]=false; } } }
我一开始写的：
if(startIndex>=nums.length) { res.add(new ArrayList<>(path)); return; }
这样对吗？这样不对啊，因为你是要存入[4,7],[4,7,7],[4,7,7,8],所以你不需要返回，而是路径上的所有节点，都得被存入res里
所以按道理来说不写终止条件是可以的，就和子集问题一样
正确的情况应该是：
if(path.size()>1) { res.add(path); }
然后这里还有一个hs不remove的为什么
class Solution { //很明显要starIndex ArrayList<Integer>path=new ArrayList<>(); List<List<Integer>> res=new ArrayList<>(); public List<List<Integer>> findSubsequences(int[] nums) { back(nums, 0); return res; } void back(int []nums,int startIndex) { if(path.size()>1) { res.add(new ArrayList<>(path)); } HashSet<Integer>hs=new HashSet<>(); for(int i=startIndex;i<nums.length;i++) { if(!path.isEmpty()&&path.get(path.size()-1)>nums[i]||hs.contains(nums[i])) { continue; } hs.add(nums[i]); path.add(nums[i]); back(nums, i+1); path.remove(path.size()-1);//为什么hs这里没有remove呢，因为你hs并不是全局变量，而是只记录每一层，相当于每一层一个hs } } }
排列吗，那就不用starIndex了，每次从头开始，但是你得跳过已经在path里面的，所以需要used
鉴定为易啊
class Solution { List<List<Integer>> result = new ArrayList<>();// 存放符合条件结果的集合 LinkedList<Integer> path = new LinkedList<>();// 用来存放符合条件结果 boolean[] used; public List<List<Integer>> permute(int[] nums) { used=new boolean[nums.length]; back(nums); return result; } void back(int []nums) { if(path.size()==nums.length) { result.add(new ArrayList<>(path)); return; } for(int i=0;i<nums.length;i++) { if(used[i]) { continue; } used[i]=true; path.add(nums[i]); back(nums); used[i]=false; path.remove(path.size()-1); } } }
怎么去重和子集问题是一个套路
class Solution { //存放结果 List<List<Integer>> result = new ArrayList<>(); //暂存结果 List<Integer> path = new ArrayList<>(); public List<List<Integer>> permuteUnique(int[] nums) { boolean []used=new boolean[nums.length]; Arrays.sort(nums); back(nums, used); return result; } void back(int[]nums,boolean[]used) { if(path.size()==nums.length) { result.add(new ArrayList<>(path)); return; } for(int i=0;i<nums.length;i++) { if(i>0&&nums[i]==nums[i-1]&&!used[i-1]) { continue; } //这里还得判断自己用没用过 if(used[i]==false) { used[i]=true; path.add(nums[i]); back(nums, used); path.remove(path.size()-1); used[i]=false; } } } }
有一说一难点不在思考本身，而是在处理二维数组和check
class Solution { //思路：首先棋盘是二维数组，但是输出形式是每个棋盘是一维数组，所以需要二维转一维String数组的函数 //然后需要检查斜线，所以还需要check函数 //然后back，应该是一行一行放 List<List<String>> res = new ArrayList<>(); public List<List<String>> solveNQueens(int n) { char[][] board = new char[n][n]; for (char[] c : board) { Arrays.fill(c, '.'); } back(n, 0, board); return res; } void back(int n,int row,char[][]board) { if(row==n) { res.add(Array2List(board)); return; } for(int i=0;i<n;i++) { if(isValid(row, i, n, board)) { board[row][i]='Q'; back(n, row+1, board); board[row][i]='.';//回溯 } } } public boolean isValid(int row,int col,int n,char[][]board) { for(int i=0;i<row;i++) { if(board[i][col]=='Q') return false; } for(int j=0;j<row;j++) { if(board[row][j]=='Q') return false; } for(int i=row-1,j=col-1;i>=0&&j>=0;i--,j--) { if(board[i][j]=='Q') return false; } for(int i=row-1,j=col+1;i>=0&&j<=n-1;i--,j++) { if(board[i][j]=='Q') return false; } return true; } public List Array2List(char[][]board) { List<String> list=new ArrayList<>(); for(char[]c:board) { list.add(String.copyValueOf(c)); } return list; } }