跳至主要內容

3.5 回溯算法

定义

回溯算法是一种通过逐步构建解决方案，遍历所有可能的候选解空间以找到解的方法。它通常用于解决组合优化问题，如排列问题、子集问题、组合问题等，这些问题可以被描述为在搜索树中找到一条路径，该路径表示问题的解。

回溯算法的基本思想是逐步构建候选解，每次尝试一个候选解中的元素，然后检查该候选解是否满足问题的要求。如果满足要求，则继续向下探索更深层次的候选解；如果不满足要求，则回溯到上一个状态，尝试其他的候选解。通过不断地深入和回溯，最终可以找到所有符合条件的解，或者找到最优解。

回溯算法通常采用递归的方式实现，每一层递归代表了解空间树的一个节点。在每一层递归中，都需要进行以下步骤：

  1. 选择：从候选解空间中选择一个元素作为当前层的候选解。
  2. 探索：根据选择的候选解，继续向下递归探索下一层的候选解。
  3. 回溯：如果当前路径无法满足问题的要求，或者已经达到问题的边界条件，则回溯到上一层，尝试其他的候选解。

回溯算法通常与剪枝技术结合使用，以避免不必要的搜索，提高搜索效率。剪枝技术可以根据问题的特点，在搜索过程中排除一些不可能满足要求的候选解，从而减少搜索空间，加快算法的执行速度。

代码示例

电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

电话号码
电话号码

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：

输入：digits = ""
输出：[]
示例 3：

输入：digits = "2"
输出：["a","b","c"]

提示：

0 <= digits.length <= 4
digits[i] 是范围 ['2', '9'] 的一个数字。

private static final String[] KEYS = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

public List<String> letterCombinations(String digits) {
    List<String> combinations = new ArrayList<>();
    if (digits == null || digits.length() == 0) {
        return combinations;
    }
    doCombination(new StringBuilder(), combinations, digits);
    return combinations;
}

private void doCombination(StringBuilder prefix, List<String> combinations, final String digits) {
    if (prefix.length() == digits.length()) {
        combinations.add(prefix.toString());
        return;
    }
    int curDigits = digits.charAt(prefix.length()) - '0';
    String letters = KEYS[curDigits];
    for (char c : letters.toCharArray()) {
        prefix.append(c);                         // 添加
        doCombination(prefix, combinations, digits);
        prefix.deleteCharAt(prefix.length() - 1); // 删除
    }
}

复原 IP 地址

题目来源：https://leetcode.com/problems/restore-ip-addresses/description/open in new window

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

示例 1：

输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]
示例 2：

输入：s = "0000"
输出：["0.0.0.0"]
示例 3：

输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

解题代码示例如下：

public List<String> restoreIpAddresses(String s) {
    List<String> addresses = new ArrayList<>();
    StringBuilder tempAddress = new StringBuilder();
    doRestore(0, tempAddress, addresses, s);
    return addresses;
}

private void doRestore(int k, StringBuilder tempAddress, List<String> addresses, String s) {
    if (k == 4 || s.length() == 0) {
        if (k == 4 && s.length() == 0) {
            addresses.add(tempAddress.toString());
        }
        return;
    }
    for (int i = 0; i < s.length() && i <= 2; i++) {
        if (i != 0 && s.charAt(0) == '0') {
            break;
        }
        String part = s.substring(0, i + 1);
        if (Integer.valueOf(part) <= 255) {
            if (tempAddress.length() != 0) {
                part = "." + part;
            }
            tempAddress.append(part);
            doRestore(k + 1, tempAddress, addresses, s.substring(i + 1));
            tempAddress.delete(tempAddress.length() - part.length(), tempAddress.length());
        }
    }
}

参考

https://www.pdai.tech/md/algorithm/alg-core-backtracking.html#数字键盘组合open in new window

上次编辑于: