算法训练——回溯算法（LeetCodeHOT100）

摘要

主要是的分析介绍leetcode中的算法题目。

一、回溯算法总结：

总结：子集、组合类问题，关键是用一个 start 参数来控制选择列表！！最后回溯六步走：

1、画出递归树，找到状态变量(回溯函数的参数)，这一步非常重要※

2、根据题意，确立结束条件

3、找准选择列表(与函数参数相关),与第一步紧密关联※

4、判断是否需要剪枝

5、作出选择，递归调用，进入下一层

6、撤销选择

二、算法练习

剑指 Offer II 087. 复原 IP 

package 回溯算法;

import java.util.ArrayList;
import java.util.List;

public class restoreIpAddressesV2 {

    public List restoreIpAddressesV2(String s) {
        int count = 4;
        int[] segment = new int[count];
        List list = new ArrayList();
        int segid = 0;
        int index = 0;
        dfsv2(s, segid, index, segment, list, count);
        return list;
    }

    private void dfsv2(String s, int segid, int index, int[] segment, List list, int count) {
        //如果是segid=4 && index=s.lenegth
        if (segid == count) {
            if (index == s.length()) {
                StringBuilder sb = new StringBuilder();
                for (int i = 0; i < count; i++) {
                    sb.append(segment[i]);
                    if (i != count - 1) {
                        sb.append('.');
                    }
                }
                list.add(sb.toString());
            }
            return;
        }
        // 当遍历完成了就返回
        if (index == s.length()) {
            return;
        }
        // 当该数字为0的时候
        if (s.charAt(index) == '0') {
            segment[segid] = 0;
            dfsv2(s, segid + 1, index + 1, segment, list, count);
        }
        int num = 0;
        for (int i = index; i < s.length(); i++) {
            num = num * 10 + (s.charAt(i) - '0');
            // 不能等于0
            if (num > 0 && num