回溯算法解决排列/组合/子集问题

数据结构与算法
3.1k 词

前言

最近学习了动态规划和回溯，发现他们的本质其实都是对二/多叉树的遍历而已，而动态规划一般再后序位置拿到子问题的解合并为大问题的解，而回溯是再前序添加路径，后序删除路径。

介绍

这次我来好好总结一些回溯算法，我认为回溯就是一种暴力穷举法，进行不同的选择时，每个选择还可以进行各种选择，回溯算法本质是在遍历树枝，应用回溯算法来解决问题其实就是在遍历一颗决策树，树的节点上放置着正确答案，你只需要拿到这些答案，问题就解决了。

对于一颗决策树，有三个重要的问题:

  1. 路径(track): 遍历经过的节点，其实就是做出的选择
  2. 选择列表(candidates): 可以做的选择，在每个节点上都可以进行
  3. 结束条件(base case): 到达回溯树的底部，无法继续做出选择

回溯算法框架：

public class BacktrackingAlgorithm {

    public static void main(String[] args) {
        // 调用回溯函数
        backtrack(0);
    }

    public static void backtrack(int k) {
        if (isSolution(k)) {
            // 处理找到的解
        } else {
            // 生成候选项集
            int[] candidates = generateCandidates(k);

            // 针对每个候选项进行递归
            for (int i = 0; i < candidates.length; i++) {
                // 做出选择
                makeChoice(k, candidates[i]);

                // 递归到下一步
                backtrack(k + 1);

                // 撤销选择
                undoChoice(k, candidates[i]);
            }
        }
    }

    public static boolean isSolution(int k) {
        // 判断是否达到问题的解
        // 根据具体问题定义
        return false;
    }

    public static void makeChoice(int k, int candidate) {
        // 做出选择
        // 根据具体问题定义
    }

    public static void undoChoice(int k, int candidate) {
        // 撤销选择
        // 根据具体问题定义
    }

    public static int[] generateCandidates(int k) {
        // 生成候选项集
        // 根据具体问题定义
        return new int[0];
    }
}

回溯算法的核心就在于做出选择、撤销选择和选对正确的结束条件。

我们再将其抽象简化后：

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

回溯算法应用在排列/组合/子集问题非常常见，例如：

在【46.全排列】问题中,不仅用到了回溯算法，而且还需要用到used数组来记录之前使用过的元素，避免重复。

那么我们接下来就具体分析一下这三类问题的异同点吧！

首先，我认为组合问题是子集问题的子问题，为什么这么说呢？其实子集只是要求出各个长度大小的组合问题而已，无非就是结束条件(base case)不一样罢了，后面我们就都把这两个问题放在一起了。

其次，排列就比较简单了，只需要遍历，且记录不用用过的元素就好，如果有重复元素，额外使用一个数组空间来记录，并且进行判断即可。

总结

对于这三种回溯形式，元素是否可重，是否可复选，我们将其分为三种形式：

1.元素无重不可复选

即元素nums中的元素是唯一的，且每个元素只能被使用一次。

组合/子集

void backtrack(int[] nums, int start) {
    // 回溯算法标准框架
    for (int i = start; i < nums.length; i++) {
        // 做选择
        track.addLast(nums[i]);
        // 注意参数
        backtrack(nums, i + 1);
        // 撤销选择
        track.removeLast();
    }
}

排列

void backtrack(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        // 剪枝逻辑
        if (used[i]) {
            continue;
        }
        // 做选择
        used[i] = true;
        track.addLast(nums[i]);

        backtrack(nums);
        // 撤销选择
        track.removeLast();
        used[i] = false;
    }
}

2.元素可重不可复选

即 nums 中的元素可以存在重复，每个元素最多只能被使用一次

组合/子集

Arrays.sort(nums);
/* 组合/子集问题回溯算法框架 */
void backtrack(int[] nums, int start) {
    // 回溯算法标准框架
    for (int i = start; i < nums.length; i++) {
        // 剪枝逻辑，跳过值相同的相邻树枝
        if (i > start && nums[i] == nums[i - 1]) {
            continue;
        }
        // 做选择
        track.addLast(nums[i]);
        // 注意参数
        backtrack(nums, i + 1);
        // 撤销选择
        track.removeLast();
    }
}

排列

Arrays.sort(nums);
/* 排列问题回溯算法框架 */
void backtrack(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        // 剪枝逻辑
        if (used[i]) {
            continue;
        }
        // 剪枝逻辑，固定相同的元素在排列中的相对位置
        if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
            continue;
        }
        // 做选择
        used[i] = true;
        track.addLast(nums[i]);

        backtrack(nums);
        // 撤销选择
        track.removeLast();
        used[i] = false;
    }
}

元素无重可复选

即 nums 中的元素都是唯一的，每个元素可以被使用若干次

组合/子集

/* 组合/子集问题回溯算法框架 */
void backtrack(int[] nums, int start) {
    // 回溯算法标准框架
    for (int i = start; i < nums.length; i++) {
        // 做选择
        track.addLast(nums[i]);
        // 注意参数
        backtrack(nums, i);
        // 撤销选择
        track.removeLast();
    }
}

排列

/* 排列问题回溯算法框架 */
void backtrack(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        // 做选择
        track.addLast(nums[i]);
        backtrack(nums);
        // 撤销选择
        track.removeLast();
    }
}

回溯归于树类问题，只要会了树的遍历，其实回溯只是在遍历时，进行选择/撤销选择，在各个节点间的树枝上游走，最后产生各样的路径。

留言