回溯算法

发表于

回溯算法是一种穷举方法，也是递归过程的一种，目标是在所有可能的情况中找出符合要求的解。当发现当前的解不符合要求时进行回退，退到上一个状态重新开始选择。

回溯算法最重要的就是包含三个元素：终止条件，剪枝条件，递归过程。以LeetCode第93题复原IP地址为例介绍回溯的基本模板。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        Stack<String> stack = new Stack<>();
        restoreIpAddresses(s, 0, res, stack);
        return res;
    }

    /**
     * 回溯算法
     *
     * @param s     题目参数
     * @param start 回溯算法一般都需要一个记录当前位置或者说进度的参数
     * @param res   结果存放的集合
     * @param stack 存放每一步产生的中间解，不一定符合题目条件
     */
    private void restoreIpAddresses(String s, int start, List<String> res, Stack<String> stack) {
        //终止条件
        //当stack中存放的数字小于4的时候显然不能构成解，接着向下求解
        //当stack中存放的数字个数等于4的时候判断当前位置是否走完了整个string
        //当栈中存放了4个数字且当前位置也走完了整个string就把结果放到res中
        //否则回溯到之前的状态，求下一个可能的解
        if (stack.size() == 4) {
            if (start == s.length()) {
                res.add(String.join(".", stack));
            }
            return;
        }
        //因为ip地址每个段对多三位所以可以对string分别按1,2,3位进行分割
        for (int i = 1; i <= 3; i++) {
            //如果当前位置+分割长度大于整个字符串的长度
            //或者说下一个分割点的长度大于字符串的长度
            //这种情况显然不能进行分割
            if (start + i > s.length()) {
                break;
            }
            String temp = s.substring(start, start + i);
            //剪枝条件
            //对截取的段进行判断是否能构成ip段
            //ip段可以为0~255之间的任意数字，但是01这种字符串是非法的需要剪枝
            if ((temp.startsWith("0") && temp.length() > 1) || 
                    Integer.parseInt(temp) > 255) {
                continue;
            }
            stack.push(temp);
            restoreIpAddresses(s, start + i, res, stack);
            //一定记得恢复现场，回退到上一步
            stack.pop();
        }
    }
}

常见的回溯算法基本可以按照这个模板进行编写，唯一改变的就是终止条件和剪枝条件。