回溯算法中常见的使用方法逻辑整理

回溯算法常见的使用方法逻辑整理

1. 回溯算法特点

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

2. 回溯算法通用方法

用回溯算法解决问题的一般步骤：

针对所给问题，定义问题的解空间，它至少包含问题的一个（最优）解。
确定易于搜索的解空间结构,使得能用回溯法方便地搜索整个解空间。
以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。

回溯是经过修改的深度优先查找方法，过程包括：对一个状态空间树进行深度优先查找，检查每个节点是否满足条件。如果不满足就回溯到该节点的父节点。算法框架(伪代码)如下：

result = []
backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

3. 常见面试题

一些总结

3.1 单词搜索

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1：
在这里插入图片描述

输入：board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCCED”
输出：true

示例 2：
在这里插入图片描述

输入：board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “SEE”
输出：true

示例 3：
在这里插入图片描述

输入：board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCB”
输出：false

解法

递归参数：当前元素在矩阵 board 中的行列索引 i 和 j ，当前目标字符在 word 中的索引 k 。
终止条件：
- 返回 false ： (1) 行或列索引越界或 (2) 当前矩阵元素与目标字符不同或 (3) 当前矩阵元素已访问过（ (3) 可合并至 (2) ）。
- 返回 true ： k = len(word) - 1 ，即字符串 word 已全部匹配。
递推工作：
- 标记当前矩阵元素：将 board[i][j] 修改为空字符 ‘’ ，代表此元素已访问过，防止之后搜索时重复访问。
- 搜索下一单元格：朝当前元素的上、下、左、右四个方向开启下层递归，使用或连接（代表只需找到一条可行路径就直接返回，不再做后续 DFS ），并记录结果至 res 。
- 还原当前矩阵元素：将 board[i][j] 元素还原至初始值，即 word[k] 。
返回值：返回布尔量 res ，代表是否搜索到目标字符串。

在这里插入图片描述

代码示例

class Solution {
    public boolean exist(char[][] board, String word) {
        char[] words = word.toCharArray();
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[0].length; j++) {
                if (dfs(board, words, i, j, 0)) return true;
            }
        }
        return false;
    }
    boolean dfs(char[][] board, char[] word, int i, int j, int k) {
        if (i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != word[k]) return false;
        if (k == word.length - 1) return true;
        board[i][j] = '\0';
        boolean res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) || 
                      dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i , j - 1, k + 1);
        board[i][j] = word[k];
        return res;
    }
}

3.2 分割回文串

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。

示例 1：

输入：s = “aab”
输出：[[“a”,“a”,“b”],[“aa”,“b”]]

示例 2：

输入：s = “a”
输出：[[“a”]]

解法

由于需要求出字符串 sss 的所有分割方案，因此我们考虑使用搜索 + 回溯的方法枚举所有可能的分割方法并进行判断。

假设我们当前搜索到字符串的第 iii 个字符，且 s[0…i−1] 位置的所有字符已经被分割成若干个回文串，并且分割结果被放入了答案数组 ans 中，那么我们就需要枚举下一个回文串的右边界 jjj，使得 s[i…j] 是一个回文串。

因此，我们可以从 iii 开始，从小到大依次枚举 jjj。对于当前枚举的 jjj 值，我们使用双指针的方法判断 s[i…j] 是否为回文串：如果 s[i…j]是回文串，那么就将其加入答案数组 ans 中，并以 j+1j+1j+1 作为新的 i 进行下一层搜索，并在未来的回溯时将 s[i…j] 从 ans 中移除。

如果我们已经搜索完了字符串的最后一个字符，那么就找到了一种满足要求的分割方法。

代码示例

class Solution {
    boolean[][] f;
    List<List<String>> ret = new ArrayList<List<String>>();
    List<String> ans = new ArrayList<String>();
    int n;

    public List<List<String>> partition(String s) {
        n = s.length();
        f = new boolean[n][n];
        for (int i = 0; i < n; ++i) {
            Arrays.fill(f[i], true);
        }

        for (int i = n - 1; i >= 0; --i) {
            for (int j = i + 1; j < n; ++j) {
                f[i][j] = (s.charAt(i) == s.charAt(j)) && f[i + 1][j - 1];
            }
        }

        dfs(s, 0);
        return ret;

    }

    public void dfs(String s, int i) {
        if (i == n) {
            ret.add(new ArrayList<String>(ans));
            return;
        }
        for (int j = i; j < n; ++j) {
            if (f[i][j]) {
                ans.add(s.substring(i, j + 1));
                dfs(s, j + 1);
                ans.remove(ans.size() - 1);
            }
        }
    }
}

3.3 全排列

给定一个不含重复数字的数组 nums ，返回其所有可能的全排列。你可以按任意顺序返回答案。

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

输入：nums = [1]
输出：[[1]]

代码示例

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> input = new ArrayList<>();
        for (int i: nums) input.add(i);
        List<Integer> tmp = new ArrayList<>();
        dfs(input, result, tmp, nums.length);
        return result;
    }

    public void dfs(List<Integer> input, List<List<Integer>> result, List<Integer> temp, int k){
        if(temp.size()==k) {
            result.add(temp);
            return;
        }
        for(int i=0;i<input.size();i++){
            List<Integer> copyInput=new ArrayList<>(input);
            List<Integer> copyTemp=new ArrayList<>(temp);
            copyTemp.add(input.get(i));
            copyInput.remove(i);
            dfs(copyInput,result,copyTemp,k);
        }
    }
}

3.4 子集

给你一个整数数组 nums ，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。你可以按任意顺序返回解集。

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

解法思路

整体上跟跳跃游戏一致，只是稍作变通

代码示例

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        dfs(0, nums, res,new ArrayList<Integer>());
        return res;
    }

    public void dfs(int i, int[] nums, List<List<Integer>> res,  ArrayList<Integer> tmp) {
        res.add(new ArrayList<>(tmp));
        for(int j = i; j < nums.length;j++) {
            tmp.add(nums[j]);
            dfs(j + 1, nums, res, tmp);
            tmp.remove(tmp.size() -1);
        }
    }
}

3.5 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

在这里插入图片描述

示例 1：

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

输入：digits = “”
输出：[]
示例 3：

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

代码示例

class Solution {
    public List<String> letterCombinations(String digits) {
        // 定义相关数字和字母的mapping关系
        Map<String, String[]> map = new HashMap<String, String[]>(){{
            put("2", new String[]{"a","b","c"});
            put("3", new String[]{"d","e","f"});
            put("4", new String[]{"g","h","i"});
            put("5", new String[]{"j","k","l"});
            put("6", new String[]{"m","n","o"});
            put("7", new String[]{"p","q","r","s"});
            put("8", new String[]{"t","u","v"});
            put("9", new String[]{"w","x","y","z"});
        }};
        // 逃出条件1：什么都没有输入，返回空
        if(digits.length() == 0) {
            return new ArrayList<>();
        }
        // 逃出条件2: 只输入1个数字，返回对应的mapping字母列表
        if(digits.length() == 1) {
            List<String> arrayList = new ArrayList<>(map.get(digits).length);
            Collections.addAll(arrayList, map.get(digits));
            return arrayList;
        }
        String[] strList = digits.split("");
        // 构造递归条件，将完整的输入拆分成2部分
        String[] first = map.get(strList[0]);
        String rest = "";
        for(int i = 1;i < strList.length;i++) {
            rest += strList[i];
        }
        
        List<String> result = new ArrayList<>();
        // 分别进行拼凑，进行递归所有的数字
        for(int i=0;i<first.length;i++) {
            List<String> tmp = letterCombinations(rest);
            for(int j = 0;j<tmp.size();j++) {
                result.add(first[i] + tmp.get(j));
            }
        }
        return result;
    }
}

3.6 组合总和

给你一个无重复元素的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有不同组合，并以列表形式返回。你可以按任意顺序返回这些组合。

candidates 中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。
示例 2：

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3：

输入: candidates = [2], target = 1
输出: []

代码示例

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(candidates);
        dfs(candidates, target, res, 0, new ArrayList<Integer>());
        return res;
    }

    public void dfs(int[] candidates, int target, List<List<Integer>> res, int i ,List<Integer> tmp) {
        if(target < 0) return;
        if(target == 0) {
            res.add(new ArrayList<>(tmp));
            return;
        }   

        for(int start = i; start < candidates.length;start++) {
            tmp.add(candidates[start]);
            dfs(candidates, target - candidates[start], res,start, tmp);
            tmp.remove(tmp.size() - 1);
        }
    }
}

3.7 括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。

示例 1：

输入：n = 3
输出：[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]

示例 2：

输入：n = 1
输出：[“()”]

代码示例

class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        """
        :type n: int
        :rtype: List[str]
        """
        global result
        result = []
        bracket_str = ""
        self.find_bracket(n, n, bracket_str)
        print(result)
        return result

    def find_bracket(self, left, right, bracket_str):
        """
        """
        global result
        if left == 0 and right == 0:
            result.append(bracket_str)
        if left > right:
            return

        if left > 0:
            self.find_bracket(left - 1, right, bracket_str + '(')
        if right > 0:
            self.find_bracket(left, right - 1, bracket_str + ')')