回溯法-排列，组合

回溯法

回溯法是一类特殊优先搜索，它记录节点状态，并在搜索完成后回溯状态。

leetcode46

分析

全排列问题，可以通过交换元素的方式在同一个数组完成，节省内存空间。
为了避免重复排列，限定待交换下标大等于当前下标。
为了不影响后序交换元素，通过递归实现遍历之后，将交换的下标回溯回之前的状态。

源码

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<Integer> output = new ArrayList<>();
        for (int num : nums) {
            output.add(num);
        }
        int n = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        backtrack(output, res, 0, n);
        return res;
    }
    
    private void backtrack(List<Integer> output, List<List<Integer>> res, int first, int n) {
        if (first == n) {
            res.add(new ArrayList<>(output));
            return;
        }

        for (int i = first; i < n; i++) {
            Collections.swap(output, i, first); // 交换当前位置与之后的所有位置
            backtrack(output, res, first + 1, n);
            Collections.swap(output, i, first); // 回溯交换状态
        }
    }
}

leetcode 77

分析

组合问题。排列回溯的是数组中交换的元素下标。组合回溯的是元素本身。

源码

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> temp = new ArrayList<>();

    public List<List<Integer>> combine(int n, int k) {
        dfs(1, n, k);
        return ans;
    }
    private void dfs(int cur, int n, int k) {
        
        if (temp.size() == k) {
            ans.add(new ArrayList<>(temp));
            return;
        }

        for (int i = cur; i <= n; i++) {
            temp.add(i);
            dfs(i + 1, n, k);
            temp.removeLast();
        }
    }
}

leetcode79

分析

回溯的是元素是否被访问这个状态，从而避免重复访问元素。

源码

class Solution {
    boolean found = false;
    boolean[][] visited;
    public boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;
        visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dfs(board, word, 0, i, j);
            }
        }
        return found;
    }
    private void dfs(char[][] board, String word, int pos, int curI, int curJ) {
        if (curI < 0 || curI >= board.length || curJ < 0 || curJ >= board[0].length) {
            return;
        }
        if (visited[curI][curJ] || word.charAt(pos) != board[curI][curJ] || found) {
            return;
        }
        if (pos == word.length() - 1) {
            found = true;
            return;
        }
        visited[curI][curJ] = true;
        dfs(board, word, pos + 1, curI + 1, curJ);
        dfs(board, word, pos + 1, curI - 1, curJ);
        dfs(board, word, pos + 1, curI, curJ + 1);
        dfs(board, word, pos + 1, curI, curJ - 1);
        visited[curI][curJ] = false;
    }
}