LeetCode刷题—回溯算法

发表于 2021-02-15 更新于 2021-02-23 分类于 LeetCode刷题

回溯算法

前言

「回溯是递归的副产品，只要有递归就会有回溯」，所以回溯法也经常和二叉树遍历，深度优先遍历（\(dfs\)）混在一起，因为这两种方式都是用了递归。

回溯法就是暴力搜索，优化回溯算法只有「剪枝」一种方法。

回溯算法能解决如下问题：

组合问题：N个数里面按一定规则找出k个数的集合
排列问题：N个数按一定规则全排列，有几种排列方式
切割问题：一个字符串按一定规则有几种切割方式
子集问题：一个N个数的集合里有多少符合条件的子集
棋盘问题：N皇后，解数独等等

解决一个回溯问题，实际上就是一个决策树的遍历过程。你只需要思考 3 个问题：

1、路径：也就是已经做出的选择。

2、选择列表：也就是你当前可以做的选择。

3、结束条件：也就是到达决策树底层，无法再做选择的条件。

代码的框架：

result = [];//结果集
void backtracking(路径，选择列表) {
    if (结束条件) {
        result.add(路径)；//存放结果
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        做选择;
        backtracking(路径，选择列表); // 递归
        回溯，撤销选择
    }
}

其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」。

使用两个变量： res 和 path，res 表示最终的结果，path 保存已走过的路径。当满足结束条件，即到达了决策树的底层，就把 path 放到 res 中。

此总结参考于 labuladong的算法小抄和代码随想录。

组合问题

77，组合，medium

给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

示例:

输入: n = 4, k = 2
输出:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

题解

n 相当于树的宽度， k 相当于树的高度。

由上面框架，选择一个数就填入路径集path，结束条件：路径集path大小 = k。

在每层递归如何选择数呢？需要变量 index 记录下一层递归的起始位置，index + 1 ~ n即为下层递归的选择列表。

代码

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        backtrack(n, k, 1, new ArrayList<>());
        return res;
    }
    public void backtrack(int n, int k, int index, List<Integer> path){
        if(path.size() == k){
            res.add(new ArrayList<>(path));
            return;
        }
        //横向遍历
        for(int i = index; i <= n ; i++){
            path.add(i);
            backtrack(n, k, i + 1, path);
            path.remove(path.size() - 1);
        }
    }
}

这里还可以进行优化，会将效率提高不少。若 n = 5, k = 4，现在 path.size() = 1，那还需 k - path.size() = 3 个数。若 index = 4，则只能选取 5，不满足，故 i 有限制条件。i <= n - (k - path.size()) + 1，即在集合n中至多要从该起始位置 : n - (k - path.size()) + 1开始遍历。

组合总和

216，组合总和Ⅲ，medium

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

所有数字都是正整数。解集不能包含重复的组合。示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]

示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]

题解

借鉴上一题的思路，组合中的数字为 1~9，则从1 开始分层遍历，结束条件即为和为 n 且 path.size() = k。选择操作：将 i 添入路径，并加入和sum 中，撤销操作反之。

代码

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    int sum = 0;
    public List<List<Integer>> combinationSum3(int k, int n) {
        backtracking(n, k, new ArrayList<>(), 1);
        return res;
    }
    public void backtracking(int n, int k, List<Integer> path, int index){
        if(sum == n && path.size() == k){
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i = index; i <= 9 ; i++){
            path.add(i);
            sum += i;
            backtracking(n, k, path, i + 1);
            sum -= i;
            path.remove(path.size() - 1);
        }
    }
}

39，组合总和，medium

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

所有数字（包括 target）都是正整数。解集不能包含重复的组合。

示例 1：

输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[
  [7],
  [2,2,3]
]

示例 2：

输入：candidates = [2,3,5], target = 8,
所求解集为：
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

提示：

1 <= candidates.length <= 30 1 <= candidates[i] <= 200 candidate 中的每个元素都是独一无二的。 1 <= target <= 500

题解

题意：在无重复元素的数组中可重复选取元素使其和为target，结果集中的数组不重复。

此题的难点在于不产生重复组合。

错误：

for(int i = 0; i < candidates.length; i++){
    ...
    backtracking(i,...);
    ...
}

如果不使用 index，最后结果会有重复数组，如 [[2,2,3],[2,3,2],[3,2,2],[7]] 。

解决：仍需要 index，以使下一次选择的起点在当前选择的基础上，这样就不会选到本次选择同层左边的数。

正确：

for(int i = index; i < candidates.length; i++){
    ...
    backtracking(index,...);
    ...
}

规律：若只在一个集合中选取组合，需要开始索引 index，如此题和上面两题。

如果是多个集合取组合，各个集合之间相互不影响，那么就不用 index，如 17。

结束条件： sum == target 时填入路径，sum > target 时舍弃。

代码

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    int sum = 0;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        backtracking(candidates, target, 0, new ArrayList<>());
        return res;
    }
    public void backtracking(int[] candidates, int target, int index, List<Integer> path){
        if(sum > target) return;
        if(sum == target){
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i = index; i < candidates.length; i++){
            path.add(candidates[i]);
            sum += candidates[i];
            backtracking(candidates, target, i, path);
            sum -= candidates[i];
            path.remove(path.size() - 1);
        }
    }
}

40，组合总和Ⅱ，medium

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明：

所有数字（包括目标数）都是正整数。解集不能包含重复的组合。示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
  [1,2,2],
  [5]
]

题解

与39题比较：

39题数组元素无重复，可重复选取，解集无重复

40题数组元素有重复，不可重复选取，解集无重复

关键在于「去重」，对此题构成的树，从上而下的同一树枝可以有重复元素，同一树层之间不可以有重复元素。如数组[1,1,2]（为方便理解已排序），target = 3 时构成的树如图

那么怎么区分树层的重复元素和树枝的重复元素呢？

使用boolean 数组 used，初始化为false，当选取元素改为true。

首先对数组进行排序，若相邻元素相等且前一元素已被同一树层使用过，跳过。代码表示为：

if(i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false)
    continue;

在图中将used的变化用橘黄色标注上，可以看出在candidates[i] == candidates[i - 1]相同的情况下：

used[i - 1] == true，说明同一树支candidates[i - 1]使用过
used[i - 1] == false，说明同一树层candidates[i - 1]使用过

代码

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    int sum = 0;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {             boolean[] used = new boolean[candidates.length];
        Arrays.fill(used, false);
        //先排序使相同元素处于相邻位置
        Arrays.sort(candidates);
        backtracking(candidates, target, 0, new ArrayList<>(), used);
        return res;
    }
    public void backtracking(int[] candidates, int target, int index, List<Integer> path, boolean[] used){
        if(sum > target) return;
        if(sum == target){
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i = index; i < candidates.length ; i++){
            //同一树层不可以重复
            if(i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false)
                continue;   
            
            path.add(candidates[i]);
            sum += candidates[i]; 
            used[i] = true;
            backtracking(candidates, target, i + 1, path, used);
            used[i] = false;
            sum -= candidates[i];
            path.remove(path.size() - 1);
        }
    }
}

多个集合求组合

17，电话号码的字母组合，medium

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

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

示例 1：

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

示例 2：

输入：digits = ""
输出：[]

示例 3：

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

题解

与上面题目不同，本题是在多个集合中找组合，不需要开始索引 index。

此题需要注意的地方有很多：

数字与字母的映射——可以用数组或Map
结束条件怎么表示？用 idx 表示遍历到digits 的数字索引（即树的深度），当 idx == digits.length() 时，结束。

Image
怎么选择？对每个数字digit 对应的字母集letter 进行遍历，选择 letter 中的字母。

代码

class Solution {
    List<String> res = new ArrayList<>();
    String[] str = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};//0-9对应字母集
    public List<String> letterCombinations(String digits) {
        if(digits.length() == 0) return res;
        backtracking(digits, new StringBuffer(), 0);
        return res;
    }
    public void backtracking(String digits, StringBuffer path, int idx){
        if(idx == digits.length()){
            res.add(path.toString());
            return;
        }
        int digit = digits.charAt(index) - '0';     // 将index指向的'数字'转为int
        String letter = str[digit]; 				// 第 index 个数字对应的字母集
        for(int i = 0; i < letter.length(); i++){
            path.append(letter.charAt(i));			//选择
            backtracking(digits, path, idx + 1);  //对下一层处理
            path.deleteCharAt(path.length() - 1);   //撤销选择
        }
    }
}

细节

StringBuffer 与 String 加入字母的区别：

因为StringBuffer传入的都是同一个对象，所以在递归完成之后必须撤回上一次的操作，需要删除上一次添加的字符。而String每次改变之后传入的都是不同的对象。故无需撤销操作。

for(int i = 0 ; i < letters.length() ; i ++){
	backtracking(digits, index + 1, s + letters.charAt(i));
}

int 与 char 类型的转换

char 不能直接转为int，得到是‘3’的Ascii，如

public static void main(String[] args) {
	char numChar = '3';
    int intNum = (int)numChar;
    System.out.println(numChar + ": " + intNum);
}

输出为：

3：51

char 转为 int 的正确方法是：

public static void main(String[] args) {
	char numChar = '3';
    int intNum = numChar - ‘0’;
    System.out.println(numChar + ": " + intNum);
}

输出为：

3：3

而 int 可以强转为 char

int a = 9;
char b = (char)a; //b = '9'

子集问题

78，子集，medium

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

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

示例 1：

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

示例 2：

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

提示：

1 <= nums.length <= 10 -10 <= nums[i] <= 10 nums 中的所有元素互不相同

题解

与上面组合问题不同在于「子集」是这棵树的所有节点，而不是只有叶子节点。

解中不含重复子集，则取过的元素不会重复取，for 循环的开始索引 index，而不是 0。

那结束条件是什么呢？可以不需要加终止条件，因为index >= nums.size()，本层for循环本来也结束了。

「求取子集问题，不需要任何剪枝！因为子集就是要遍历整棵树」。

根据上面的模板有

代码

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        backtracking(nums, 0, new ArrayList<>());
        return res;
    }
    public void backtracking(int[] nums, int index, List<Integer> path){
        //不需结束条件
        res.add(new ArrayList<>(path));
        for(int i = index; i < nums.length; i++){
            path.add(nums[i]);
            backtracking(nums, i + 1, path);
            path.remove(path.size() - 1);
        }
    }
}

90，子集Ⅱ，medium

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

输入: [1,2,2]
输出:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

题解

与 78 题的区别：

78题 —— 数组不含重复元素，解不含重复子集。
90题 —— 数组含重复元素，解不含重复子集。

此题与 40题类似，解题思路也一致。

同一树层不能取相同元素（否则解中的子集会重复），而同一树枝可以有相同元素。

使用boolean数组 used ，初始化为false，当选取元素改为true。

首先对数组进行排序，若相邻元素相等且前一元素已被同一树层使用过，跳过。

代码

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        boolean[] used = new boolean[nums.length];
        Arrays.sort(nums);
        backtracking(nums, 0, used, new ArrayList<>());
        return res;
    }
    public void backtracking(int[] nums, int index, boolean[] used, List<Integer> path){
        res.add(new ArrayList<>(path));
        for(int i = index; i < nums.length; i++){
            if(i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false)
                continue;
            path.add(nums[i]);
            used[i] = true;
            backtracking(nums, i + 1, used, path);
            used[i] = false;
            path.remove(path.size() - 1);
        }
    }
}

491，递增子序列，medium

给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。

示例:

输入: [4, 6, 7, 7]
输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]

题解

首先判断此题的「去重」与 40、90题不同，上面的做法是将数组先排序再去重，防止同一层的相同元素重复使用，使解中出现重复子集。但此题要求递增子序列，不可打乱顺序。

采用 HashSet 去重，记录同层使用过的元素。

如果当前元素在 set 中有重复元素，则跳过。

那怎么保证递增呢？

如果当前元素小于上一个选取的元素，则跳过。

代码

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> findSubsequences(int[] nums) {
        backtracking(nums, 0, new ArrayList<>());
        return res;
    }
    public void backtracking(int[] nums, int idx, List<Integer> path){
        //结束条件
        if(path.size() > 1){
            res.add(new ArrayList<>(path));
            //注意此处没有return
        }
        Set<Integer> set = new HashSet<>();
        for(int i = idx; i < nums.length; i++){
            //当同层有相同元素已经在set中，或要加入的nums[i] < 上一个加入的元素时
            if(!path.isEmpty() && nums[i] < path.get(path.size() - 1) || set.contains(nums[i]))
            continue;
            
            set.add(nums[i]);
            path.add(nums[i]);
            backtracking(nums, i + 1, path);
            path.remove(path.size() - 1);
        } 
    }
}

细节

set 定义在递归函数上面，为了确保本层不选取重复元素。新的一层 set 都会重新定义（清空），所以要知道 set 只负责本层！

因为递增序列中至少两个元素，所以 path.size() > 1 才添加到 res 中，注意不能写 return，因为要记录树的所有节点。

添加 return 返回的结果为：

[[4,7],[4,6],[7,7],[6,7]]

小总结

如果给定数组中包含重复元素 / 组合和子集问题中要求解中不含重复结果 / 在一个集合中找组合，就需要开始索引 idx 对同层元素去重。（77，39，216，40）

子集问题不需要剪枝，因为要返回所有可能集合。不需要return。

切割问题

131，分割回文串，medium

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回 s 所有可能的分割方案。

示例:

输入: "aab"
输出:
[
  ["aa","b"],
  ["a","a","b"]
]

题解

不能重复截取，所以仍需要 idx。

结束条件：分割线到字符串末尾，将path填入 res 中。
选择：如果当前形成的字符串[idx,i] 不是回文串，跳过。是则进行递归。

代码

class Solution {
    List<List<String>> res = new ArrayList<>();
    public List<List<String>> partition(String s) {
        backtracking(new ArrayList<String>(), s, 0);
        return res;
    }
    public void backtracking(List<String> path, String s, int idx){
        //遍历完成
        if(idx == s.length()){
            res.add(new ArrayList<String>(path));
            return;
        }
       
        for(int i = idx; i < s.length(); i++){
             //子串 [idx,i]
            String str = s.substring(idx, i + 1);
            //如果不是回文，跳过
            if(!isPalindrome(str)){
                continue;
            }         
            path.add(str);
            backtracking(path, s, i + 1);
            path.remove(path.size() - 1);
        }
        
    }
    //判断是不是回文字符串
    public boolean isPalindrome(String str){
        int left = 0;
        int right = str.length() - 1;
        while(left < right){
            if(str.charAt(left) != str.charAt(right))
                return false;
            left++;
            right--;
        }
        return true;
    }
}

排列问题

46，全排列，medium

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

题解

不需要idx：解中的组合是有序的，例如：在同一树层已经选择了 1，下一次选择还可以选 1，即 [2,1] ≠[1,2]。所以不需要 idx。
使用boolean 数组 used：全排列，组合中没有重复数字，同一树枝上不能重复选择。用used 数组记录当前元素是否已被选择。

结束条件：当递归到树的叶子节点结束，path 添加到res 中。

代码

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        boolean[] used = new boolean[nums.length];
        backtracking(nums, used, new ArrayList<>());
        return res;
    }
    public void backtracking(int[] nums, boolean[] used, List<Integer> path){
        int n = nums.length;
        //结束条件
        if(path.size() == n){
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i = 0; i < n; i++){
            //如果一个树枝上的元素已被选择（path已有nums[i]），跳过
            if(used[i] == true) continue;

            path.add(nums[i]);
            used[i] = true;
            backtracking(nums, used, path);
            used[i] = false;
            path.remove(path.size() - 1);
        }
    }
}

排列问题的不同：

因为解中的数组是有序的，每层都是从0开始搜索而不是startIndex
需要used数组记录path里都放了哪些元素了

47，全排列Ⅱ，medium

给定一个可包含重复数字的序列 nums ，按任意顺序返回所有不重复的全排列。

示例 1：

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

示例 2：

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

题解

与46题的区别

此题有重复数字，则在同一层不能选取相同数字，否则会出现重复排列。类似 40题的思路来去重。

在同一树枝中，同一个数字不能被重复选，需要通过 used[i] 判断是否已被选取过。

代码

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        boolean[] used = new boolean[nums.length];
        //先排序
        Arrays.sort(nums);
        backtracking(nums, new ArrayList<>(), used);
        return res;
    }
    public void backtracking(int[] nums, List<Integer> path, boolean[] used){
        if(path.size() == nums.length){
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i = 0; i < nums.length; i++){
            //同一层相同元素已被选取，跳过
            if(i > 0 && used[i - 1] == false && nums[i] == nums[i - 1]) continue;
            //同一枝同一元素已被选取，跳过
            if(used[i] == true) continue;

            path.add(nums[i]);
            used[i] = true;
            backtracking(nums, path, used);
            used[i] = false;
            path.remove(path.size() - 1);
        }
    }
}

总结

注意解中有序和无序的区别：在组合、子集、切割问题中，一个集合的问题，需要开始索引 idx。排列问题从 0 开始遍历。

注意同一层的重复元素和同一树枝的重复元素的区别：常借用 boolean数组记录被选择的元素，进行去重。

注意结束条件：树的节点，所有节点或叶子节点或满足题意的节点。

其他

22，括号生成，medium

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

示例 1：

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

示例 2：

输入：n = 1
输出：["()"]

提示：

1 <= n <= 8

题解

选择：将左括号或右括号填入path。

结束条件：当左括号和右括号都用完了，或 path.length() == 2 * n 就结束。

遍历过程：

剪枝：当选择的右括号数量 > 左括号。
选择：当选择的左括号数量 < n，填入左括号；右括号同。

代码

class Solution {
    List<String> res = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        backtracking(n, 0, 0, new StringBuilder());
        return res;
    }
    //l 表示已填入path 的左括号数量，r 表示已填入path 的右括号数量
    public void backtracking(int n, int l, int r, StringBuilder path){
        //结束条件
        // if(path.length() == 2 * n){
        if(l == n && r == n){
            res.add(path.toString());
            return;
        }
        //已选择的左括号数量 < 右括号，剪枝
        if(l < r) return;
        if(l < n){
            path.append("(");
            backtracking(n, l + 1, r, path);//向下递归
            path.deleteCharAt(path.length() - 1);
        }
        if(r < n){
            path.append(")");
            backtracking(n, l, r + 1, path);
            path.deleteCharAt(path.length() - 1);
        }
    } 
}

图的回溯

二维图可看作多个子节点多个分支，进行深度遍历搜索得到结果。

容易与【岛屿问题】混淆，岛屿问题用 DFS 来解，图的问题与岛屿问题有什么区别呢？下面由具体题目来体会。

79，单词搜索，medium

给定一个二维网格和一个单词，找出该单词是否存在于网格中。

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

示例:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]
给定 word = "ABCCED", 返回 true
给定 word = "SEE", 返回 true
给定 word = "ABCB", 返回 false

题解

一开始当做岛屿问题来做，为了避免每次DFS的时候被搜过的地方再重复搜索，修改已经搜索过的网格为 '.'。

给定 word = "ABCB"时就会发现，第一次dfs后的结果为：

[
  ['.','.','.','E'],

  ['S','F','C','S'],

  ['A','D','E','E']
]

矩阵发生了变化，不能再继续搜索到 ABC 了。这时候就想到用回溯，修改了状态再改回来就好了嘛。

一段官方点的说法：DFS前后必须要保证执行前后程序面对问题的状态是相同的，因此当前问题缩小为子问题时所做的对当前问题状态产生影响的事情应该全部失效，这就是所谓的回溯时还原现场。

直接写回溯可能会超时，还可以进行优化，也就是【剪枝】。

当已经找到路径时，不需再回溯。

代码

class Solution {
    public boolean exist(char[][] board, String word) {
        int rows = board.length;
        int columns = board[0].length;
        for(int i = 0; i < rows; i++){
            for(int j = 0; j < columns; j++){
                if(backtracking(board, word, i, j, 0))
                    return true;
            }
        }
         return false;
     }
    public boolean backtracking(char[][] board, String word, int i, int j, int idx){
        boolean res = false;
        //结束条件：不在合法区域 或  当前字符与目标不一致
        if(!isValidArea(board, i, j) || board[i][j] != word.charAt(idx)){
            return false;
        }
        //搜索完单词
        if(idx == word.length() - 1){
            res = true;
            return true;
        }

        //还没找到全部路径
        if(!res){
            char temp = board[i][j];
            board[i][j] = '.';
            //向四个方向搜索
            boolean r1 = backtracking(board, word, i + 1, j, idx + 1);
            boolean r2 = backtracking(board, word, i , j + 1, idx + 1);
            boolean r3 = backtracking(board, word, i - 1, j, idx + 1); 
            boolean r4 = backtracking(board, word, i, j - 1, idx + 1); 
            board[i][j] = temp;
            return r1 || r2 || r3 || r4;
        }
        return true;
     }
    public boolean isValidArea(char[][] image, int sr, int sc){
        if(sr < 0 || sr >= image.length || sc < 0 || sc >= image[0].length)
            return false;
        return true;
    }
}

------ 本文结束感谢您的阅读 ------