回溯是 DFS 的一种，它不是用在遍历图的节点上，而是用于求解 排列组合 问题，例如有 { ‘a‘,‘b‘,‘c‘ } 三个字符，求解所有由这三个字符排列得到的字符串。
在程序实现时，回溯需要注意对元素进行标记的问题。使用递归实现的回溯，在访问一个新元素进入新的递归调用，此时需要将新元素标记为已经访问，这样才能在继续
递归调用时不用重复访问该元素；但是在递归返回时，需要将该元素标记为未访问，因为只需要保证在一个递归链中不同时访问一个元素，而在不同的递归链是可以访问
已经访问过但是不在当前递归链中的元素。
回溯算法的标准格式：
回溯法伪代码 back(c,digits,offset,res){ if(offset==length){ res.add(); return; } for(char c:String.toCharArray()){ back(c,digits,offset+1,res); } }
leetcode 17
最终代码
class Solution { public static final String[] key={"","","abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; // 回溯法伪代码 // back(c,digits,offset,res){ // if(offset==length){ // res.add(); // return; // } // for(char c:String.toCharArray()){ // back(c,digits,offset+1,res); // } // } public List<String> letterCombinations(String digits) { List<String> res=new ArrayList<>(); if(digits!=null&&digits.length()!=0){ back("",digits,0,res); } return res;//如果最终结果不对，可以直接诊断return附近哪里逻辑写错了 } public void back(String pre,String digits,int offset,List<String> res){ if(offset==digits.length()){ res.add(pre); return; } String letters=key[digits.charAt(offset)-‘0‘]; for(char ch:letters.toCharArray()){ back(pre+ch,digits,offset+1,res); } } }
leetcode 79
这道题也毫无疑问地用回溯的迷宫找路完整版模版 back(c,digits,offset,res){ if(offset==length){ res.add(); return; } for(char c:String.toCharArray()){ back(c,digits,offset+1,res); } } ****************************************** exit(){ for (int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(back()) return res; } } } back(char[][] board, String word, int start, int x, int y){ if(start==word.length){ return true; } //越界等找不到满足条件的路径的时候 if(x<0||x>m||y<0||y<n||vis[][]==true||board[x][y]!=word.charAt(start)){ return false; } board[x][y]=true; for(int i=0;i<4;i++){ int nextx=x+dir[i][0]; int nexty=y+dir[i][1]; if(back(board,word,start+1,nextx,nexty)) return true; } //最重要的是如果四个方向都没有找到合适的路径，说明当前路径不合适，则应该对访问值进行回归 vis[x][y]=false; return false; }
本题的完整版代码：
class Solution { // 这道题也毫无疑问地用回溯的迷宫找路完整版模版 // back(c,digits,offset,res){ // if(offset==length){ // res.add(); // return; // } // for(char c:String.toCharArray()){ // back(c,digits,offset+1,res); // } // } // ****************************************** // exit(){ // for (int i=0;i<m;i++){ // for(int j=0;j<n;j++){ // if(back()) return res; // } // } // } // back(char[][] board, String word, int start, int x, int y){ // if(start==word.length){ // return true; // } // //越界等找不到满足条件的路径的时候 // if(x<0||x>m||y<0||y<n||vis[][]==true||board[x][y]!=word.charAt(start)){ // return false; // } // board[x][y]=true; // for(int i=0;i<4;i++){ // int nextx=x+dir[i][0]; // int nexty=y+dir[i][1]; // if(back(board,word,start+1,nextx,nexty)) return true; // } // //最重要的是如果四个方向都没有找到合适的路径，说明当前路径不合适，则应该对访问值进行回归 // vis[x][y]=false; // return false; // } public int[][] dir={{1,0},{-1,0},{0,1},{0,-1}}; public boolean exist(char[][] board, String word) { int m=board.length; int n=board[0].length; boolean[][] vis=new boolean[m][n]; for (int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(back(board,word,0,i,j,vis)) return true; } } return false; } public boolean back(char[][] board, String word, int start, int x, int y,boolean[][] vis){ int m=board.length; int n=board[0].length; if(start==word.length()){ return true; } //越界等找不到满足条件的路径的时候 if(x<0||x>=m||y<0||y>=n||vis[x][y]==true||board[x][y]!=word.charAt(start)){ return false; } vis[x][y]=true; for(int i=0;i<4;i++){ int nextx=x+dir[i][0]; int nexty=y+dir[i][1]; if(back(board,word,start+1,nextx,nexty,vis)) return true; } //最重要的是如果四个方向都没有找到合适的路径，说明当前路径不合适，则应该对访问值进行回归 vis[x][y]=false; return false; } }
原文：https://www.cnblogs.com/sjh-dora/p/12929810.html