解题思路

这题的解题思路和上面的组合总和是差不多的，唯一不同的是元素「不能被重复遍历」，使用一个变量记录遍历的起始值，遍历过的数据，下次往后一位开始遍历。

代码如下：

class Solution {

    List> list = new ArrayList<>();

 int[] candidate;

    public List> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
  candidate = candidates;
  recall(0,target,new LinkedList<>());
  return list;
    }

    private void recall(int start, int target, LinkedList path) {
 if (target == 0) {
  list.add(new ArrayList<>(path));
  return;
 }
 for (int i = start; i  start && candidate[i] == candidate[i-1]) {
   continue;
  }
  int sub = target - candidate[i];
  if (sub < 0) {
   break;
  }
  path.add(candidate[i]);
  recall(i + 1,sub,path);
  path.removeLast();
 }
     }
}

❝

start 记录遍历的起始值，其他解题方法和上面的组合求和是类似的。题目还有一个要求是不能出现重复的组合，就需要判断 candidate[i] == candidate[i-1] 就忽略该数据，往后继续遍历。

❞

46.全排列

解题思路

• 每个元素都需要遍历一遍。
• 遍历元素的时，遍历完第一数，继续遍历未遍历的数据。
• 遍历结束后，返回上一个分叉。

代码整理如下：

class Solution {
    List> result = new ArrayList<>();

    LinkedList path = new LinkedList<>();

    boolean[] used;

    public List> permute(int[] nums) {
        if (nums.length == 0) {
            return result;
        }
        used = new boolean[nums.length];
        permuteHelper(nums);
        return result;
    }

    private void permuteHelper(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]);
            permuteHelper(nums);
            path.removeLast();
            used[i] = false;
        }
    }
}

❝

使用 used 记录哪些数据遍历过，遍历过的数据不会遍历，其他也是使用递归搜索。

❞

51.N皇后

题目描述

解题思路

N 皇后问题是一个经典的回溯算法问题,是面试比较常见的问题。在一个 n * n 的棋盘上，每个格子放入的元素后，查看是够有同行、同列、左上方以及右上方是否冲突，冲突就回溯，不冲突就继续往下遍历。

• 初始化数组，默认初始值。
• 每一行只能放一个 Q,不冲突后，再遍历下一列的数据（因为同一行不能冲突）。
• 因为每一行只放一个 Q，所以不存在同行冲突。判断冲突就潘丹同一列、左上方以及右上方是否有冲突。
• 遍历到最后一行时，记录符合条件的数据。

class Solution {

    List> res = new ArrayList<>();

    public List> solveNQueens(int n) {
        // 初始化棋盘 "." 表示空，"Q"表示皇后，
  char[][] board = new char[n][n];
  for (char[] c : board) {
   Arrays.fill(c, '.');
  }
  backtrack(board, 0);
  return res;
    }

    private void backtrack(char[][] board, int row) {
  //终止条件
  if (row == board.length) {
   res.add(charToList(board));
   return;
  }
  //每一行列数(也就是长度)
  int n = board[row].length;
  for (int col = 0; col < n; col++) {
   //排除相互攻击的格子
   if (!isValid(board,row,col)) {
    continue;
   }
   //放入Q
   board[row][col] = 'Q';
   //进入下一行放皇后
   backtrack(board,row + 1);
   //撤销Q
   board[row][col] = '.';
  }
   }

   private boolean isValid(char[][] board, int row, int col) {
  int n = board.length;
  //检查列是否有皇后冲突
  for (int i = 0; i < n; i++) {
   if (board[i][col] == 'Q') {
    return false;
   }
  }
  //检查右上方是否有皇后冲突
  for (int i = row - 1,j = col + 1; i >= 0 && j < n; i--,j++) {
   if (board[i][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;
   }
  }
  return true;
 }

 public List charToList(char[][] board) {
  List list = new ArrayList<>();
  for (int i = 0; i < board.length; i++) {
   list.add(String.copyValueOf(board[i]));
  }
  return list;
 }
}

总结

回溯算法尝试在问题的解空间中搜索可能的解，并在搜索过程中进行选择、撤销选择和终止搜索，直到找到解或确定无解为止。

• 通常通过递归函数来实现回溯算法。
• 在每一步，需要做出选择（选择一个分支）然后递归地探索该选择的结果。
• 在递归返回后，需要撤销之前的选择，以便继续探索其他分支。
• 使用条件语句或循环来控制选择的范围和条件。