目标和
设置全局变量：
class Solution {int ret,path,aim;public int findTargetSumWays(int[] nums, int target) {aim = target;dfs(nums,0);return ret;}public void dfs(int[] nums,int pos){if(pos == nums.length){if(path == aim){ret ++;}return;}path += nums[pos];dfs(nums,pos+1);path -= nums[pos];path -= nums[pos];dfs(nums,pos+1);path += nums[pos];}
}将path作为局部参数：
class Solution {int ret,aim;public int findTargetSumWays(int[] nums, int target) {aim = target;dfs(nums,0,0);return ret;}public void dfs(int[] nums,int pos,int path){if(pos == nums.length){if(path == aim){ret ++;}return;}dfs(nums,pos+1,path+nums[pos]);dfs(nums,pos+1,path-nums[pos]);}
}39. 组合总和 - 力扣（LeetCode）
法一：每一个位置都能从数组中数中选择；
class Solution {int aim;List<List<Integer>> ret;List<Integer> path;public List<List<Integer>> combinationSum(int[] nums, int target) {path = new ArrayList<>();ret = new ArrayList<>();aim = target;dfs(nums,0,0);return ret;}public void dfs(int[] nums,int pos,int sum){if(sum == aim){ret.add(new ArrayList<>(path));return;}if(sum > aim || pos == nums.length){return;}for(int i = pos;i < nums.length;i++){path.add(nums[i]);dfs(nums,i,sum+nums[i]);path.remove(path.size()-1);}}
}法二：针对数组中的数字的数量来进行选择；
对于一号位置元素，可以选择一个，两个，三个；
对于二号位置元素，可以选择一个，两个，三个；
。。。。。。
class Solution {int aim;List<List<Integer>> ret;List<Integer> path;public List<List<Integer>> combinationSum(int[] nums, int target) {path = new ArrayList<>();ret = new ArrayList<>();aim = target;dfs(nums,0,0);return ret;}public void dfs(int[] nums,int pos,int sum){if(sum == aim){ret.add(new ArrayList<>(path));return;}if(sum > aim || pos == nums.length){return;}for(int k = 0;k *nums[pos]<= aim;k++){if(k!=0){path.add(nums[pos]);}dfs(nums,pos+1,sum+k*nums[pos]);}for(int k = 1;k *nums[pos]<= aim;k++){path.remove(path.size()-1);}
}
}784. 字母大小写全排列 - 力扣（LeetCode）
class Solution {StringBuffer path;List<String> ret;public List<String> letterCasePermutation(String s) {path = new StringBuffer();ret = new ArrayList<>();dfs(s,0);return ret;}public void dfs(String s,int pos){if(pos == s.length()){ret.add(path.toString());return;}char ch = s.charAt(pos);path.append(ch);dfs(s,pos+1);path.deleteCharAt(path.length()-1);if(ch < '0' || ch >'9'){char tmp = change(ch);path.append(tmp);dfs(s,pos+1);path.deleteCharAt(path.length()-1);}}public char change(char ch){if(ch >= 'a' && ch <= 'z' ) return ch-=32;else return ch += 32;}
}526. 优美的排列 - 力扣（LeetCode）
class Solution {boolean[] check;int ret; public int countArrangement(int n) {check = new boolean[n+1];//数组的小标从1开始计数dfs(n,1);return ret;}public void dfs(int n,int pos){if(pos == n+1){ret ++;return;}for(int i = 1 ; i <= n;i++){if(check[i] == false && (i % pos == 0 || pos % i == 0)){check[i] = true;dfs(n,pos+1);check[i] = false;}}}
}51. N 皇后 - 力扣（LeetCode）
从行的角度来考虑问题：
类似哈希表的策略来处理考虑当前位置能否放皇后的问题。
1、考虑该列是否存在皇后，设置一个布尔数组，每一行有皇后就变为true。
2、主对角线：主对角线用y=x+b表示。---->y-x=b;
及判断该位置的函数为：
y-x=b或者y-x+n=b+n；
yinyongb这个定值来映射这一条主对角线
3、副对角线:主对角线用y=-x+b表示。---->y+x=b;
及判断该位置的函数为：
y+x=b;
class Solution {boolean[] checkCol,checkDig1,checkDig2;//每一列，住对角，副对角List<List<String>> ret;char[][] path;int n;public List<List<String>> solveNQueens(int n1) {n = n1;checkCol = new boolean[n];checkDig1 = new boolean[n*2];checkDig2 = new boolean[n*2];ret = new ArrayList<>();path = new char[n][n];for(int i = 0;i < n;i++){Arrays.fill(path[i],'.');}dfs(0);return ret;}public void dfs(int row){if(row == n){List<String> tmp = new ArrayList<>();for(int i = 0;i < n;i++){tmp.add(new String(path[i]));}ret.add(new ArrayList<>(tmp));}//考虑m每一列能不能放for(int col = 0;col <n;col++){//某行的该列判断能不能放if(checkCol[col] == false && checkDig1[row-col+n] == false && checkDig2[row+col] == false){path[row][col]='Q';checkCol[col]=checkDig1[row-col+n]=checkDig2[row+col] = true;dfs(row+1);//恢复path[row][col]='.';checkCol[col]=checkDig1[row-col+n]=checkDig2[row+col] = false;}}}
}36. 有效的数独 - 力扣（LeetCode）
col[9][1]：表示第九列是否包含有1这个数字 ;
class Solution {boolean[][] row,col;boolean[][][] grid;public boolean isValidSudoku(char[][] board) {row = new boolean[9][10];col = new boolean[9][10];grid =new boolean[9][9][10];for(int i = 0;i < 9 ;i++){for(int j = 0;j <9;j++){if(board[i][j] != '.'){int num = board[i][j] -'0';if(row[i][num] || col[j][num] || grid[i/3][j/3][num]){return false;}row[i][num] = col[j][num] = grid[i/3][j/3][num] = true;}}}return true;}
}37. 解数独 - 力扣（LeetCode）
class Solution {boolean[][] row,col;boolean[][][] grid;public void solveSudoku(char[][] board) {row = new boolean[9][10];col = new boolean[9][10];grid =new boolean[9][9][10];//标记数据初始化for(int i = 0;i < 9 ;i++){for(int j = 0;j <9;j++){if(board[i][j] != '.'){int num = board[i][j] -'0';row[i][num] = col[j][num] = grid[i/3][j/3][num] = true;}}}dfs(board);}public boolean dfs(char[][] board){for(int i = 0;i < 9 ;i++){for(int j = 0;j <9;j++){if(board[i][j] == '.'){//填数for(int num =1;num <= 9; num++){//剪纸if(!row[i][num] && !col[j][num] && !grid[i/3][j/3][num]){board[i][j]= (char)('0'+num);row[i][num] = col[j][num] = grid[i/3][j/3][num] = true;if(dfs(board) == true){return true;}//返回现场board[i][j] = '.';row[i][num] = col[j][num] = grid[i/3][j/3][num] = false;}}return false;}}}return true;}
}79. 单词搜索 - 力扣（LeetCode）
class Solution {boolean[][] vis;int m,n;char[] word;public boolean exist(char[][] board, String word1) {m= board.length;n = board[0].length;vis = new boolean[m][n];word = word1.toCharArray();for(int i = 0;i < m ;i++){for(int j = 0;j <n;j++){if(board[i][j] == word[0] ){vis[i][j] = true;if(dfs(board,i,j,1)){return true;}vis[i][j] = false;} }}return false;}int[] dx={0,0,1,-1};int[] dy={1,-1,0,0};public boolean dfs(char[][] board,int i,int j,int pos){if(pos == word.length){return true;}//上下左右去匹配//利用向量数组，为位置定义四个上下左右位置。for(int k = 0;k < 4;k++){int x = i + dx[k],y = j + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && board[x][y] == word[pos]){vis[x][y] = true;if(dfs(board,x,y,pos+1)){return true;}vis[x][y] = false;} }return false;}
}1219. 黄金矿工 - 力扣（LeetCode）
class Solution {boolean[][] vis;int m,n;int[] dx={0,0,1,-1};int[] dy={1,-1,0,0};int ret;public int getMaximumGold(int[][] g) {m = g.length;n = g[0].length;vis = new boolean[m][n];for(int i = 0;i < m ;i++){for(int j = 0;j <n;j++){if(g[i][j] !=0){vis[i][j] = true;dfs(g,i,j,g[i][j]);vis[i][j] = false;}}}return ret;}public void dfs(int[][] g,int i,int j,int path){ret = Math.max(ret,path);for(int k = 0;k < 4;k++){int x = i + dx[k],y = j + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && g[x][y] != 0){vis[x][y] = true;dfs(g,x,y,path+g[x][y]);vis[x][y] = false;}}}
}980. 不同路径 III - 力扣（LeetCode）
class Solution {boolean[][] vis;int m,n,step,ret;int[] dx={0,0,1,-1};int[] dy={1,-1,0,0};public int uniquePathsIII(int[][] grid) {m= grid.length;n = grid[0].length;vis = new boolean[m][n]; //开始位置int bx = 0;int by = 0;for(int i = 0;i < m ;i++){for(int j = 0;j <n;j++){if(grid[i][j] == 0 ){step ++;}else if(grid[i][j] == 1){bx = i;by = j;}}}step +=2;vis[bx][by] = true;dfs(grid,bx,by,1);return ret;}public void dfs(int[][] grid,int i,int j,int count){if(grid[i][j] == 2){if(count == step){ret++;}return;}for(int k = 0;k < 4;k++){int x = i + dx[k],y = j + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y] != -1){vis[x][y] = true;dfs(grid,x,y,count+1);vis[x][y] = false;} }}
} ps:谢谢观看。
