滑动窗口算法

• 回溯算法框架
• 回溯算法运用

图片来源于网络

1. 回溯算法框架

回溯算法，是类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。

回溯算法框架：解决一个回溯问题，实际上就是一个决策树的遍历过程。需要思考3个问题：

• 路径：已经做出的选择。
• 选择列表：当前可以做的选择。
• 结束条件：到达决策树底层，无法再做选择的条件。

回溯算法的代码框架：

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return

    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」。

2. 回溯算法运用

2.1 全排列问题

力扣 46 题如下：

全排列

上面题目，比如给三个数 [1,2,3]，可画出如下决策树：

决策树

其中，上图中标红的 [2] 就是 路径，记录已经做过的选择；[1,3] 就是 选择列表，表示当前可以做出的选择；结束条件 就是遍历到树的底层，在这里是选择列表为空的时候。

定义的 backtrack 函数其实就像一个指针，在这棵树上游走，同时要正确维护每个节点的属性，每当走到树的底层，其「路径」就是一个全排列。如下：

正确维护每个节点的属性

只要在递归之前做出选择，在递归之后撤销刚才的选择，就能正确得到每个节点的选择列表和路径"：

for 选择 in 选择列表:
    # 做选择
    将该选择从选择列表移除
    路径.add(选择)
    backtrack(路径, 选择列表)
    # 撤销选择
    路径.remove(选择)
    将该选择再加入选择列表

通过回溯算法框架实现全排列代码如下：

    /**
     * 全排列：输入一组不重复的数字，返回它们的全排列
     * <p>
     * 时间复杂度：O(N!)
     */
    public List<List<Integer>> permute(int[] nums) {
        // 记录「路径」
        LinkedList<Integer> track = new LinkedList<>();
        backTack(nums, track);
        return res;
    }

    List<List<Integer>> res = new LinkedList<>();

    /**
     * 路径：记录在 track 中
     * 选择列表：nums 中不存在于 track 的那些元素（没有显式记录选择列表，这边通过 nums 和 track 推导出）
     * 结束条件：nums 中的元素全都在 track 中出现
     */
    void backTack(int[] nums, LinkedList<Integer> track) {
        // 触发结束条件
        if (track.size() == nums.length) {
            res.add(new LinkedList<>(track));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            // 排除不合法的选择
            if (track.contains(nums[i])) continue;
            // 做选择
            track.add(nums[i]);
            // 进入下一层决策树
            backTack(nums, track);
            // 取消选择
            track.removeLast();
        }
    }

小结：不像动态规划存在重叠子问题可以优化，回溯算法就是纯暴力穷举，复杂度一般都很高。

2.2 N 皇后问题

力扣 51 题如下：

皇后问题

注：皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。

这个问题跟全排列问题差不多，决策树的每一层表示棋盘上的每一行；每个节点可以做出的选择是，在该行的任意一列放置一个皇后。

套用回溯算法框架如下：

    /**
     * N 皇后问题：输入棋盘边长 n，返回所有合法的放置
     */
    public List<List<String>> solveNQueens(int n) {
        // '.' 表示空，'Q' 表示皇后，初始化空棋盘。
        char[][] board = new char[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(board[i], '.');
        }
        backtrack(board, 0);
        return res2;
    }

    List<List<String>> res2 = new ArrayList<List<String>>();

    /**
     * 路径：board 中小于 row 的那些行都已经成功放置了皇后
     * 选择列表：第 row 行的所有列都是放置皇后的选择
     * 结束条件：row 超过 board 的最后一行
     */
    void backtrack(char[][] board, int row) {
        // 触发结束条件
        if (row == board.length) {
            res2.add(convertToList(board));
            return;
        }

        int n = board[0].length;
        for (int col = 0; col < n; col++) {
            // 排除不合法选择
            if (!isValid(board, row, col)) continue;
            // 做选择
            board[row][col] = 'Q';
            // 进入下一行决策
            backtrack(board, row + 1);
            // 撤销选择
            board[row][col] = '.';
        }
    }

上面部分是主要代码，其中 isValid 函数的实现如下：

    /**
     * 是否可以在 board[row][col] 放置皇后？
     */
    boolean isValid(char[][] board, int row, int col) {
        int n = board[0].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;
    }

    /**
     * char[][] 转成 List<String>
     */
    List<String> convertToList(char[][] board) {
        List<String> list = new ArrayList<>();
        for (char[] chars : board) {
            list.add(new String(chars));
        }
        return list;
    }

小结：回溯算法就是个多叉树的遍历问题，关键就是在前序遍历和后序遍历的位置做一些操作，写 backtrack 函数时，需要维护走过的「路径」和当前可以做的「选择列表」，当触发「结束条件」时，将「路径」记入结果集。

2.3 括号生成

力扣 22 题如下：

括号生成

有关括号问题，有如下两个性质：

• 一个「合法」括号组合的左括号数量一定等于右括号数量。

• 对于一个「合法」的括号字符串组合 p，必然对于任何 0 <= i < len(p) 都有：子串 p[0..i] 中左括号的数量 >= 右括号的数量。

上面题目也可以这么理解，有 2n 个位置，每个位置可以放置字符 ( or )，组成的所有括号组合中，有多少个是合法的？套用回溯算法框架思路如下：

void backtrack(int n, int i, string& track) {
    // i 代表当前的位置，共 2n 个位置
    // 穷举到最后一个位置了，得到一个长度为 2n 组合
    if (i == 2 * n) {
        print(track);
        return;
    }

    // 对于每个位置可以是左括号或者右括号两种选择
    for choice in ['(', ')'] {
        track.push(choice); // 做选择
        // 穷举下一个位置
        backtrack(n, i + 1, track);
        track.pop(choice); // 撤销选择
    }
}

显然对于 2n 个位置，分别有 n 个左括号和右括号，这边用 left 记录还可以使用多少个左括号，用 right 记录还可以使用多少个右括号，实现代码如下：

    /**
     * 括号生成
     */
    public List<String> generateParenthesis(int n) {
        // 记录所有合法的括号组合
        List<String> res = new ArrayList<>();
        // 回溯过程中的路径
        List<Character> track = new ArrayList<>();
        // 可用的左括号和右括号数量初始化为 n
        backtrack(n, n, track, res);
        return res;
    }

    /**
     * 可用的左括号数量为 left 个，可用的右括号数量为 right 个
     */
    void backtrack(int left, int right, List<Character> track, List<String> res) {
        // 触发结束条件
        if (right < left) return;          // 若左括号剩下的多，说明不合法
        if (left < 0 || right < 0) return; // 数量小于 0 是不合法的
        if (left == 0 && right == 0) {
            // 当所有括号都恰好用完时，得到一个合法的括号组合
            StringBuilder sb = new StringBuilder();
            for (Character c : track) {
                sb.append(c);
            }
            res.add(sb.toString());
            return;
        }

        // 尝试放一个左括号
        track.add('('); // 选择
        backtrack(left - 1, right, track, res);
        track.remove(track.size() - 1); // 撤消选择

        // 尝试放一个右括号
        track.add(')'); // 选择
        backtrack(left, right - 1, track, res);
        track.remove(track.size() - 1); // 撤消选择
    }

2.4 子集问题

力扣 78 题如下：

子集

上题中返回的解集可看成是如下树的所有节点：

[1 2 3] 返回的解集

套用回溯算法实现如下：

    /**
     * 子集
     */
    public List<List<Integer>> subsets(int[] nums) {
        // 记录路径
        List<Integer> track = new ArrayList<>();
        backtrack(nums, 0, track);
        return res4;
    }

    List<List<Integer>> res4 = new ArrayList<>();

    void backtrack(int[] nums, int start, List<Integer> track) {
        res4.add(new ArrayList<>(track));
        // 注意 i 从 start 开始递增
        for (int i = start; i < nums.length; i++) {
            // 做选择
            track.add(nums[i]);
            Log.d("backtrack", "size: " + track.size());
            // 回溯
            backtrack(nums, i + 1, track);
            // 撤销选择
            track.remove(track.size() - 1);
        }
    }

2.5 子集划分问题

力扣 698 题如下：

划分为 k 个相等的子集

上面题目可用看作将 n 个数字分配到 k 个「桶」里，最后这 k 个「桶」里的数字之和要相同。

将 n 个数字分配到 k 个桶里，有两种方案：

• 以这 n 个数字的视角，每个数字都要选择进入到 k个桶中的某一个。

以数字的视角，选择 k 个桶，递归代码逻辑如下：

// k 个桶（集合），记录每个桶装的数字之和
int[] bucket = new int[k];

// 穷举 nums 中的每个数字
void backtrack(int[] nums, int index) {
    // base case
    if (index == nums.length) {
        return;
    }
    // 穷举每个桶
    for (int i = 0; i < bucket.length; i++) {
        // 选择装进第 i 个桶
        bucket[i] += nums[index];
        // 递归穷举下一个数字的选择
        backtrack(nums, index + 1);
        // 撤销选择
        bucket[i] -= nums[index];
    }
}

完善代码如下：

    /**
     * 划分为k个相等子集 -- 以数字为视角
     * 时间复杂度：O(k^n)
     */
    public boolean canPartitionKSubsets(int[] nums, int k) {
        // 排除一些基本情况
        if (k > nums.length) return false;
        int sum = 0;
        for (int num : nums) sum += num;
        if (sum % k != 0) return false;

        // 提前对nums数组降序排序，大的数字会先被分配到bucket中，
        // 对于之后的数字，bucket[i] + nums[index]会更大，更容易触发剪枝的 if 条件
        Arrays.sort(nums);
        int i = 0, j = nums.length - 1;
        for (; i < j; i++, j--) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }

        // k 个桶（集合），记录每个桶装的数字之和
        int[] bucket = new int[k];
        // 理论上每个桶（集合）中数字的和
        int target = sum / k;
        // 穷举，看看 nums 是否能划分成 k 个和为 target 的子集
        return backtrack(nums, bucket, 0, target);
    }

    /**
     * 穷举 nums 中的每个数字
     */
    boolean backtrack(int[] nums, int[] bucket, int index, int target) {
        // base case
        if (index == nums.length) {
            // 检查所有桶的数字之和是否都是 target
            for (int sum : bucket) {
                if (sum != target) {
                    return false;
                }
            }
            // nums 成功平分成 k 个子集
            return true;
        }

        // 穷举 nums[index] 可能装入的桶
        for (int i = 0; i < bucket.length; i++) {
            // 剪枝，桶装装满了
            if (bucket[i] + nums[index] > target) continue;

            //将 nums[index] 装入 bucket[i]
            bucket[i] += nums[index];
            // 递归穷举下一个数字的选择
            if (backtrack(nums, bucket, index + 1, target)) {
                return true;
            }
            // 撤销选择
            bucket[i] -= nums[index];
        }

        // nums[index] 装入哪个桶都不行
        return false;
    }

• 以这 k 个桶的视角，对于每个桶，都要遍历 nums 中的 n 个数字，然后选择是否将当前遍历到的数字装进这个桶里。

以桶的视角，需要遍历 nums 中所有数字，决定哪些数字需要装到当前桶中，若当前桶装满了（桶内数字和达到 target），则让下一个桶开始执行第 1 步，实现代码如下：

    /**
     * 划分为k个相等子集 -- 以桶为视角
     * 时间复杂度：O(k*2^n)
     */
    public boolean canPartitionKSubsets2(int[] nums, int k) {
        // 排除一些基本情况
        if (k > nums.length) return false;
        int sum = 0;
        for (int v : nums) sum += v;
        if (sum % k != 0) return false;

        boolean[] used = new boolean[nums.length];
        int target = sum / k;

        // k 号桶初始什么都没装，从 nums[0] 开始做选择
        return backtrack(nums, used, 0, 0, k, target);
    }

    boolean backtrack(int[] nums, boolean[] used, int start, int bucket, int k, int target) {
        // base case
        if (k == 0) {
            // 所有桶都被装满了，而且 nums 一定全部用完了
            // 因为 target == sum / k
            return true;
        }
        if (bucket == target) {
            // 装满了当前桶，递归穷举下一个桶的选择
            // 让下一个桶从 nums[0] 开始选数字
            return backtrack(nums, used, 0, 0, k - 1, target);
        }

        // 从 start 开始向后探查有效的 nums[i] 装入当前桶
        for (int i = start; i < nums.length; i++) {
            // 剪枝
            if (used[i]) continue; // nums[i] 已经被装入别的桶中
            if (nums[i] + bucket > target) continue; // 当前桶装不下 nums[i]

            // 做选择，将 nums[i] 装入当前桶中
            used[i] = true;
            bucket += nums[i];
            // 递归穷举下一个数字是否装入当前桶
            if (backtrack(nums, used, i + 1, bucket, k, target)) return true;

            // 撤销选择
            used[i] = false;
            bucket -= nums[i];
        }

        // 穷举了所有数字，都无法装满当前桶
        return false;
    }

2.6 组合问题

力扣 77 题如下：

组合

上面题目中 k 限制了树的高度，n 限制了树的宽度，如下所示：

n = 4, k = 2

这道题和子集问题差不多，套用回溯算法框架代码实现如下：

    /**
     * 组合
     */
    public List<List<Integer>> combine(int n, int k) {
        if (k <= 0 || n <= 0) return res5;
        // 记录路径
        List<Integer> track = new ArrayList<>();
        backtrack(n, k, 1, track);
        return res5;
    }

    List<List<Integer>> res5 = new ArrayList<>();

    void backtrack(int n, int k, int start, List<Integer> track) {
        // 到达树的底部
        if (k == track.size()) {
            res5.add(new ArrayList<>(track));
            return;
        }

        // 注意 i 从 start 开始递增
        for (int i = start; i <= n; i++) {
            // 做选择
            track.add(i);
            backtrack(n, k, i + 1, track);
            // 撤销选择
            track.remove(track.size() - 1);
        }
    }

小结：

回溯算法非常简单粗暴，可以认为是一种树的遍历问题，时间复杂度比较高。

排列问题用回溯算法时，使用 contains 方法排除已经选择的数字。

子集问题用回溯算法时，要用 start 排除已选择的数字。

组合问题用回溯算法时，要用 start 排除已选择的数字。

参考链接：

回溯算法解题套路框架

回溯算法最佳实践：括号生成

回溯算法牛逼：集合划分问题

回溯算法团灭子集、排列、组合问题