DFS + 回溯
1. 全排列
1. 特点
- 需要visited判断重复搜索
- 长度一致时出口
- 从0开始遍历,遍历过程中进行判断重复搜索和去重
- visited[i]重置
- 回溯剪枝
2. 题目
全排列,无重复:https://leetcode-cn.com/problems/permutations/
class Solution { List<List<Integer>> result = new ArrayList<>(); List<Integer> list = new ArrayList<>(); public List<List<Integer>> permute(int[] nums) { //全排列无重复 //出口:list长度和nums一致时 //从0开始遍历,需要visited判断重复搜索 if(nums.length == 0){ return result; } boolean[] visited = new boolean[nums.length]; dfs(nums,visited); return result; } public void dfs(int[] nums,boolean[] visited){ //出口 if(list.size() == nums.length){ result.add(new ArrayList<>(list)); return; } //从0开始遍历 for(int i=0;i<nums.length;i++){ //重复搜索判断 if(visited[i]){ continue; } list.add(nums[i]); visited[i] = true; dfs(nums,visited); visited[i] = false; //回溯剪枝 list.remove(list.size()-1); } } }
全排列,有重复:https://leetcode-cn.com/problems/permutations-ii/submissions/
class Solution { List<List<Integer>> result = new ArrayList<>(); List<Integer> list = new ArrayList<>(); public List<List<Integer>> permuteUnique(int[] nums) { //全排列有重复,先排序,遍历过程中去重 if(nums.length == 0){ return result; } Arrays.sort(nums); boolean[] visited = new boolean[nums.length]; dfs(nums,visited); return result; } public void dfs(int[] nums,boolean[] visited){ //出口 if(list.size() == nums.length){ result.add(new ArrayList<>(list)); return; } //从0开始遍历 for(int i=0;i<nums.length;i++){ if(visited[i]){ continue; } //前一个已经匹配,有重复 if(i>0 && nums[i]==nums[i-1] && visited[i-1]){ continue; } list.add(nums[i]); visited[i] = true; dfs(nums,visited); visited[i] = false; list.remove(list.size()-1); } } }
字符串排序:https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/submissions/
class Solution { List<String> result = new ArrayList<>(); public String[] permutation(String s) { //字符串全排列,先排序,需要visited,从0开始遍历 char[] str = s.toCharArray(); Arrays.sort(str); boolean[] visited = new boolean[str.length]; //初始temp字符串为空 dfs(str,visited,""); return result.toArray(new String[result.size()]); } public void dfs(char[] str,boolean[] visited,String temp){ if(temp.length() == str.length){ result.add(temp); return; } //从0开始遍历 for(int i=0;i<str.length;i++){ if(visited[i]){ continue; } if(i>0 && str[i]==str[i-1] && visited[i-1]){ continue; } visited[i] = true; dfs(str,visited,temp+str[i]); visited[i] = false; } } }
电话号码组合(全排列):https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/solution/
class Solution { //Map存放九宫格的数字和字母对应的kv Map<Character,String> map = new HashMap<>(); List<String> result = new ArrayList<>(); String digits; public List<String> letterCombinations(String digits) { this.digits = digits; if(digits.length() == 0){ return result; } //预存kv map.put('2', "abc"); map.put('3', "def"); map.put('4', "ghi"); map.put('5', "jkl"); map.put('6', "mno"); map.put('7', "pqrs"); map.put('8', "tuv"); map.put('9', "wxyz"); dfs(0,""); return result; } public void dfs(int index,String temp){ //出口,当temp长度等于digits时 if(temp.length() == digits.length()){ result.add(temp); return; } //提取当前数字对应的字符串 String str = map.get(digits.charAt(index)); for(int i=0;i<str.length();i++){ dfs(index+1,temp+str.charAt(i)); } } }
括号生成:https://leetcode-cn.com/problems/generate-parentheses/submissions/
class Solution { List<String> result = new ArrayList<>(); public List<String> generateParenthesis(int n) { //全排列,从n,n往左右两边扩散 dfs(n,n,""); return result; } public void dfs(int left,int right,String temp){ if(left == 0 && right == 0){ result.add(temp); return; } if(left > 0){ dfs(left-1,right,temp+"("); } if(right > left){ dfs(left,right-1,temp+")"); } } }
2. 子集
1. 特点
- 从0开始递归
- 如果有重复,先排序,遍历时去重
- 不需要出口,直接添加层存储
- 从i开始遍历
- 回溯剪枝
2. 题目
子集:https://leetcode-cn.com/problems/subsets/submissions/
class Solution { List<List<Integer>> result = new ArrayList<>(); List<Integer> list = new ArrayList<>(); public List<List<Integer>> subsets(int[] nums) { //子集,直接添加不需要出口,从i开始遍历 if(nums.length == 0){ return result; } dfs(nums,0); return result; } public void dfs(int[] nums,int index){ result.add(new ArrayList<>(list)); for(int i=index;i<nums.length;i++){ list.add(nums[i]); dfs(nums,i+1); list.remove(list.size()-1); } } }
子集(有重复):https://leetcode-cn.com/problems/subsets-ii/submissions/
class Solution { List<List<Integer>> result = new ArrayList<>(); List<Integer> list = new ArrayList<>(); public List<List<Integer>> subsetsWithDup(int[] nums) { //子集有重复,先排序,遍历时进行去重 if(nums.length == 0){ return result; } Arrays.sort(nums); dfs(0,nums); return result; } public void dfs(int index,int[] nums){ result.add(new ArrayList<>(list)); for(int i=index;i<nums.length;i++){ if(i>index && nums[i]==nums[i-1]){ continue; } list.add(nums[i]); dfs(i+1,nums); list.remove(list.size()-1); } } }
3. 组合总和
1. 特点
- 如果是组合,确定出口和可用元素
- 如果是总和,先排序进行递减,如果无重复,遍历时不用去重。如果有重复,遍历时要进行去重
- 从0开始递归
- 出口:目标值递减到0
- 从index开始遍历,判断target-nums[i]是否小于0,break
- 去重
- 添加、递归、回溯剪枝
2. 题目
组合:https://leetcode-cn.com/problems/combinations/
class Solution { List<Integer> list = new ArrayList<>(); List<List<Integer>> result = new ArrayList<>(); public List<List<Integer>> combine(int n, int k) { //出口:list长度为k //可用元素:从1到n dfs(1,n,k); return result; } public void dfs(int start,int end,int k){ if(list.size() == k){ result.add(new ArrayList<>(list)); return; } for(int i=start;i<=end;i++){ list.add(i); dfs(i+1,end,k); list.remove(list.size()-1); } } }
组合:https://leetcode-cn.com/problems/combination-sum-iii/
class Solution { List<List<Integer>> result = new ArrayList<>(); List<Integer> list = new ArrayList<>(); public List<List<Integer>> combinationSum3(int k, int n) { //出口:n递减到0,list长度为k //可用元素:1到9 dfs(1,n,k); return result; } public void dfs(int start,int n,int k){ if(n == 0 && list.size() == k){ result.add(new ArrayList<>(list)); return; } for(int i=start;i<=9;i++){ list.add(i); dfs(i+1,n-i,k); list.remove(list.size()-1); } } }
组合总和(无重复,元素可以用多次):https://leetcode-cn.com/problems/combination-sum/submissions/
class Solution { List<List<Integer>> result = new ArrayList<>(); List<Integer> list = new ArrayList<>(); public List<List<Integer>> combinationSum(int[] candidates, int target) { //类型:dfs组合总和 //思路: //1. 递归出口:target递减到0 //2. 从index开始遍历,需要递减,先排序 //3. 遍历时判断是否溢出 Arrays.sort(candidates); dfs(candidates,target,0); return result; } public void dfs(int[] candidates,int target,int index){ if(target == 0){ result.add(new ArrayList<>(list)); return; } for(int i=index;i<candidates.length;i++){ if(target - candidates[i] < 0){ break; } list.add(candidates[i]); dfs(candidates,target-candidates[i],i); list.remove(list.size()-1); } } }
组合总和(有重复,元素只能用1次):https://leetcode-cn.com/problems/combination-sum-ii/submissions/
class Solution { List<List<Integer>> result = new ArrayList<>(); List<Integer> list = new ArrayList<>(); public List<List<Integer>> combinationSum2(int[] candidates, int target) { //总和,先排序,遍历时递减顺便去重 //出口:target递减到0 //从index开始遍历 if(candidates.length == 0){ return result; } Arrays.sort(candidates); dfs(candidates,target,0); return result; } public void dfs(int[] candidates,int target,int index){ if(target == 0){ result.add(new ArrayList<>(list)); return; } for(int i=index;i<candidates.length;i++){ if(target - candidates[i] < 0){ break; } if(i > index && candidates[i]==candidates[i-1]){ continue; } list.add(candidates[i]); dfs(candidates,target-candidates[i],i+1); list.remove(list.size()-1); } } }
4. 二维
岛屿周长:https://leetcode-cn.com/problems/island-perimeter/submissions/
class Solution { public int islandPerimeter(int[][] grid) { if(grid.length == 0 || grid[0].length == 0){ return 0; } for(int i=0;i<grid.length;i++){ for(int j=0;j<grid[0].length;j++){ if(grid[i][j] == 1){ return dfs(i,j,grid); } } } return 0; } public int dfs(int row,int col,int[][] grid){ //1出口,遇到0时,周长+1,返回1 if(row < 0 || row > grid.length-1 || col < 0 || col > grid[0].length-1 || grid[row][col] == 0){ return 1; } //0出口,已经搜索过了 if(grid[row][col] == 2){ return 0; } grid[row][col] = 2; return dfs(row+1,col,grid) + dfs(row-1,col,grid) + dfs(row,col+1,grid) + dfs(row,col-1,grid); } }
岛屿数量:https://leetcode-cn.com/problems/number-of-islands/submissions/
class Solution { public int numIslands(char[][] grid) { if(grid.length == 0 || grid[0].length == 0){ return 0; } int result = 0; for(int i=0;i<grid.length;i++){ for(int j=0;j<grid[0].length;j++){ if(grid[i][j] == '1'){ dfs(i,j,grid); result++; } } } return result; } public void dfs(int row,int col,char[][] grid){ //出口 if(row < 0 || row > grid.length-1 || col < 0 || col > grid[0].length-1 || grid[row][col] == '0'){ return; } //表示已经搜索过了 grid[row][col] = '0'; //搜索上下左右 dfs(row+1,col,grid); dfs(row-1,col,grid); dfs(row,col+1,grid); dfs(row,col-1,grid); } }
岛屿面积:https://leetcode-cn.com/problems/max-area-of-island/submissions/
class Solution { public int maxAreaOfIsland(int[][] grid) { if(grid.length == 0 || grid[0].length == 0){ return 0; } int result = 0; for(int i=0;i<grid.length;i++){ for(int j=0;j<grid[0].length;j++){ //当矩阵为1时,进行dfs,提取最大值 if(grid[i][j] == 1){ result = Math.max(dfs(i,j,grid),result); } } } return result; } public int dfs(int row,int col,int[][] grid){ //0出口 if(row > grid.length-1 || row < 0 || col > grid[0].length-1 || col < 0 || grid[row][col] == 0){ return 0; } //修改为0 grid[row][col] = 0; //叠加上下左右 return 1 + dfs(row+1,col,grid) + dfs(row-1,col,grid) + dfs(row,col+1,grid) + dfs(row,col-1,grid); } }
朋友圈:https://leetcode-cn.com/problems/friend-circles/submissions/
class Solution { public int findCircleNum(int[][] M) { if(M.length == 0 || M[0].length == 0){ return 0; } boolean[] visited = new boolean[M.length]; int result = 0; for(int i=0;i<M.length;i++){ //未被搜索 if(visited[i] == false){ dfs(i,visited,M); result++; } } return result; } public void dfs(int row,boolean[] visited,int[][] M){ for(int i=0;i<M[0].length;i++){ if(visited[i] == false && M[row][i] == 1){ visited[i] = true; dfs(i,visited,M); } } } }
单词搜索:https://leetcode-cn.com/problems/word-search/submissions/
class Solution { public boolean exist(char[][] board, String word) { //搜索矩阵,不使用额外空间,保存当前位置字符,dfs之后恢复 int row = board.length; int col = board[0].length; for(int i=0;i<board.length;i++){ for(int j=0;j<board[0].length;j++){ if(dfs(i,j,board,word,0)){ return true; } } } return false; } public boolean dfs(int row,int col,char[][] board,String word,int index){ //false出口 if(row < 0 || col < 0 || row > board.length-1 || col > board[0].length-1 || board[row][col] != word.charAt(index)){ return false; } //true出口 if(index == word.length()-1){ return true; } char temp = board[row][col]; board[row][col] = '/'; boolean result = dfs(row+1,col,board,word,index+1) || dfs(row-1,col,board,word,index+1) || dfs(row,col+1,board,word,index+1) || dfs(row,col-1,board,word,index+1); board[row][col] = temp; return result; } }
机器人的运动范围:https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/
class Solution { int result = 0; public int movingCount(int m, int n, int k) { //从[0,0]到[m,n],需要visited判断重复搜索 boolean[][] visited = new boolean[m][n]; dfs(0,0,m,n,k,visited); return result; } public void dfs(int i,int j,int row,int col,int k,boolean[][] visited){ //继续递归 if(i<row && j<col && (i%10+i/10 + j%10+j/10) <= k && visited[i][j] == false){ result++; visited[i][j] = true; dfs(i+1,j,row,col,k,visited); dfs(i,j+1,row,col,k,visited); } } }