回溯

2022-03-02

字数统计: 2.1k字 | 阅读时长: 9分

模板

回溯算法，全称是回溯搜索算法，通过递归嵌套多层遍历，寻找可能的答案。

回溯三部曲

1.确定函数的返回值和参数，一般为void

void backtrack(参数)

2.确定回溯的终止条件

if（终止条件）{

保存结果

return；

}

3.确定回溯搜索的遍历

for（选择本层结集合的元素）{

处理节点；

backtrack（路径，选择列表）；

回溯，撤销处理结果；

}

回溯或递归的分析方法

画树形图

树的节点表示当前变量的状态，比如当前的path，startIndex

箭头表示传递给下一层的值 i substring，也可以是下一层传递给上层的值

分割回文串

https://leetcode.cn/problems/palindrome-partitioning/

子集问题 想错了×
并不是找到字符串子集所有回文字符串

而是找到所有分割方案，每种方案所有的字串都是回文字符串

List<String> result = new LinkedList<>();
public List<List<String>> partition(String s) {
    this.backtrack(s, 0, "");
    System.out.println(this.result);
    List<List<String>> result = new ArrayList<>();
    return result;
}

// 组合问题需要使用startIndex，使用path参数自动回溯
private void backtrack(String s, int startIndex, String path) {
    // 保存结果
    if (path.length()>0 && this.isSame(path)) {
        this.result.add(path);
    }

    // 递归终止条件省略，利用for循环的判断条件终止

    // 本层遍历方式
    for (int i=startIndex; i<s.length(); i++) {
        backtrack(s, i+1, path+s.charAt(i));
    }
}

private boolean isSame(String s) {
    int mid = (s.length() - 1) / 2;
    for (int i=0; i<=mid; i++) {
        if (s.charAt(i) != s.charAt(s.length()-1-i)) {
            return false;
        }
    }
    return true;
}

回溯
字符串子序列与子串是不一样的

子序列：当成子集问题，回溯收集所有节点

子串：必须是连续的，回溯或者循环遍历起点与终点

List<String> path = new LinkedList<>();
List<List<String>> result = new LinkedList<>();
public List<List<String>> partition(String s) {
    this.backtrack(s, 0);
    return this.result;
}

// 组合问题需要使用startIndex
private void backtrack(String s, int startIndex) {
    // 保存结果，结束递归
    if (startIndex == s.length()) {
        this.result.add(new LinkedList<>(path));
        return;
    }

    // 本层遍历方式，i表示本层提取[startIndex, i)的字符串
    for (int i=startIndex+1; i<=s.length(); i++) {
        // 当前是回文串，才会继续向下递归，否则剪枝
        String current = s.substring(startIndex, i);
        if (this.isSame(current)) {
            this.path.add(current);
            backtrack(s, i);
            this.path.remove(this.path.size()-1);
        }
    }
}

private boolean isSame(String s) {
    int mid = (s.length() - 1) / 2;
    for (int i=0; i<=mid; i++) {
        if (s.charAt(i) != s.charAt(s.length()-1-i)) {
            return false;
        }
    }
    return true;
}

子集

https://leetcode.cn/problems/subsets/

// 组合问题只收集叶子节点，子集问题收集所有节点
private List<List<Integer>> result = new ArrayList<>();
private List<Integer> path = new ArrayList<>();
public List<List<Integer>> subsets(int[] nums) {
    this.backtrack(nums, 0);
    return this.result;
}

// 组合问题，要使用startIndex
private void backtrack(int[] nums, int startIndex) {
    // path要在下一层递归的时候加入result，当前层加入reuslt的path
    // 是上一层的，要写在递归终止条件的前面，否则会漏掉叶子节点的path
    this.result.add(new ArrayList<>(this.path));
    
    // 递归终止条件，不写也没事，会在for循环判断的时候终止递归
    if (startIndex >= nums.length) {
        return;
    }

    // 单层遍历逻辑
    for (int i=startIndex; i<nums.length; i++) {
        this.path.add(nums[i]);
        backtrack(nums, i+1);
        this.path.remove(this.path.size()-1);
    }
}

单词拆分

https://leetcode.cn/problems/word-break/

回溯 超时了
其实不是回溯，只是递归，因为没有涉及处理当前节点以及回溯撤销当前节点的操作

private Set<String> set;
public boolean wordBreak(String s, List<String> wordDict) {
    this.set = new HashSet<>(wordDict);
    return this.helper(s, 0);
}

// 递归函数返回值布尔值，由于需要分割子串，需要参数s与startIndex
// 递归函数的意义很重要，理解了递归函数的意义，才能知道在什么时候调用
// 该递归函数的意义是，能否找到一种分割方案分割 s.substring(startIndex, s.length())
// 使分割形成的子串都在wordDict中
private boolean helper(String s, int startIndex) {
    // 递归结束条件，当到结尾时，说明前面分割的子串都找到了，返回true
    if (startIndex == s.length()) {
        return true;
    }

    // i的含义，分割出[startIndex, i)的子串
    for (int i=startIndex+1; i<=s.length(); i++) {
        String word = s.substring(startIndex, i);
        // 如果当前单词在wordDict中，并且后续字符串也能找到分割方案，使子串都在wordDict，返回true
        if (this.set.contains(word) && helper(s, i)) {
            return true;
        }
    }

    // 遍历完还没有找到，说明不存在分割方案，返回false
    return false;
}

记忆化递归
每个helper(s, i)都会重新计算，太耗时

比如在第一层遍历startIndex=0的时候已经计算helper(s, 2)，在下一层startIndex=1计算的时候还会再算一遍 helper(s, 2)

其实是在startIndex=1的时候首次计算的helper(s, 2)

发现不用保存为true的结果，因为找到true时，就不会继续递归了，已经找到了答案，直接返回，后续不会用到保存的true结果

private Set<String> set;
// memory记录计算的结果 memory[i] 表示[i, end)的字符串能否找找到分割方案
// -1表示初始化 0表示没找到 1表示找到了
private int[] memory; 
public boolean wordBreak(String s, List<String> wordDict) {
    this.set = new HashSet<>(wordDict);
    this.memory = new int[s.length()];
    for (int i=0; i<s.length(); i++) {
        memory[i] = -1;
    }
    return this.helper(s, 0);
}

// 递归函数返回值布尔值，由于需要分割子串，需要参数s与startIndex
// 递归函数的意义很重要，理解了递归函数的意义，才能知道在什么时候调用
// 该递归函数的意义是，能否找到一种分割方案分割 s.substring(startIndex, s.length())
// 使分割形成的子串都在wordDict中
private boolean helper(String s, int startIndex) {
    // 递归结束条件，当到结尾时，说明前面分割的子串都找到了，返回true
    if (startIndex == s.length()) {
        return true;
    }

    // 不等于-1说明已经计算过，返回是否找到
    if (this.memory[startIndex] != -1) {
        // 等于1说明找到了，不等于1说明没找到
        return this.memory[startIndex] == 1;
    }
    // i的含义，分割出[startIndex, i)的子串
    for (int i=startIndex+1; i<=s.length(); i++) {
        String word = s.substring(startIndex, i);
        // 如果当前单词在wordDict中，并且后续字符串也能找到分割方案，
        // 使子串都在wordDict，返回true
        if (this.set.contains(word)) {
            if (helper(s, i)) {
                // 防止越界，保存结果
                if (i < memory.length) {
                    memory[i] = 1;
                }
                return true;
            } else {
                // 保存结果
                memory[i] = 0;
            }
        }
    }

    // 遍历完还没有找到，说明不存在分割方案，返回false
    return false;
}

记忆化递归只保存false

private Set<String> set;
// memory记录计算的结果 memory[i] 表示[i, end)的字符串能否找找到分割方案
// 只用记录找不到的结果，因为找到的话，保存的结果也不会再用到
// true表示初始化，false表示已经计算过了 
private boolean[] memory; 
public boolean wordBreak(String s, List<String> wordDict) {
    this.set = new HashSet<>(wordDict);
    this.memory = new boolean[s.length()];
    for (int i=0; i<s.length(); i++) {
        memory[i] = true;
    }
    return this.helper(s, 0);
}

// 递归函数返回值布尔值，由于需要分割子串，需要参数s与startIndex
// 递归函数的意义很重要，理解了递归函数的意义，才能知道在什么时候调用
// 该递归函数的意义是，能否找到一种分割方案分割 s.substring(startIndex, s.length())
// 使分割形成的子串都在wordDict中
private boolean helper(String s, int startIndex) {
    // 递归结束条件，当到结尾时，说明前面分割的子串都找到了，返回true
    if (startIndex == s.length()) {
        return true;
    }

    // 不等于true说明已经计算过，返回没有找到
    if (this.memory[startIndex] != true) {
        return false;
    }
    // i的含义，分割出[startIndex, i)的子串
    for (int i=startIndex+1; i<=s.length(); i++) {
        String word = s.substring(startIndex, i);
        // 如果当前单词在wordDict中，并且后续字符串也能找到分割方案，使子串都在wordDict，返回true
        if (this.set.contains(word) && helper(s, i)) {
            return true;
        }
    }

    // 遍历完还没有找到，说明不存在分割方案，保存并返回false
    this.memory[startIndex] = false;
    return false;
}