对于模板的理解
找出可选择的列表, 遍历选择,然后递归,最后回溯也就是撤销选择
结束条件 for(选择:选择列表){ 加入选择 递归 撤销选择 }
class Solution { private List<List<Integer>> res = new LinkedList<>(); public List<List<Integer>> permute(int[] nums) { LinkedList<Integer> track = new LinkedList<>(); backtrack(nums, track); return res; } public void backtrack(int[] nums, LinkedList<Integer> track){ // 结束条件 if(track.size() == nums.length){ res.add(new LinkedList<Integer>(track)); return; } // 遍历选择列表 for(int i = 0; i < nums.length; i++){ // 剪枝 if(track.contains(nums[i])){ continue; } // 做出选择 track.add(nums[i]); // 递归 backtrack(nums, track); // 回溯 track.removeLast(); } } }
class Solution { private List<List<String>> res = new ArrayList<>(); public List<List<String>> solveNQueens(int n) { List<String> track = new ArrayList<>(); StringBuilder sb = new StringBuilder(); // 全部填充 for(int i = 0; i < n; i++){ sb.append("."); } for(int i = 0; i < n; i++){ track.add(sb.toString()); } backtrack(track, 0, n); return res; } public void backtrack(List<String> track, int row, int n){ // 结束条件 if(row == n){ res.add(new ArrayList<String>(track)); return; } // 选择列表, row这一行中所有列的位置 for(int i = 0; i < n; i++){ // 判断这些列是否能放置皇后 boolean flag = isValid(track, row, i, n); if(!flag){ continue; } // 将.替换为Q change(track, row, i, "Q"); backtrack(track, row + 1, n); change(track, row, i, "."); } } public void change(List<String>track, int row, int col, String str){ StringBuilder sb = new StringBuilder(track.get(row)); track.remove(row); sb.replace(col, col + 1, str); track.add(row, sb.toString()); } public boolean isValid(List<String>track, int row, int col, int n){ // 同一列 for(int i = 0; i < n; i++){ if(i == row){ continue; } if(track.get(i).charAt(col) == 'Q'){ return false; } } // 左上方的对角线 for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--){ if(track.get(i).charAt(j) == 'Q'){ return false; } } // 右上方的对角线 for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++){ if(track.get(i).charAt(j) == 'Q'){ return false; } } return true; } }