回溯的热门题目

L39 组合总和

给你一个 无重复元素 的整数数组 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
输出: []

提示:

  • 1 <= candidates.length <= 30
  • 2 <= candidates[i] <= 40
  • candidates 的所有元素 互不相同
  • 1 <= target <= 40

刚开始接触回溯可能这里一开始会懵,所以我们先想想刚才解答的题目113

可是,113是树,这里是数组啊?

先不急,看我们之前解决的数组问题L77

  // 针对一个结点,遍历可能的搜索起点,其实就是枚举
        for (int i = startIndex; i <= n; i++) {
            path.addLast(i);
            // 搜索起点要加1是为了缩小范围,下一轮递归做准备,因为不允许出现重复的元素
            dfs(n, k, i + 1, path, res);
            path.removeLast();
        }

没错,这里其实可以转换为N叉树,我们如果要选择数字,第一次选肯定是数字第一个,以此类推

但是这里不一样的是这里选择的数字可以重复,例如示例1,但是这里我们可以先不考虑,假设不能重复,我们应该怎么做?

很明显,如果不算重复,几乎和我们113一模一样,我们先尝试写出代码:

  1. 递归结束条件:当target不断减去数组元素<=0的时候
  2. 对数组每一个元素进行递归,因此直接使用我们回溯的模板就行了

代码实现:

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    Deque<Integer> path = new ArrayDeque<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        dfs(candidates, target, 0);
        return res;
    }

    void dfs(int[] candidates, int target, int startIndex) {
        if (target < 0)
            return;

        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = startIndex; i < candidates.length; i++) {
            path.addLast(candidates[i]);
            target -= candidates[i];
            dfs(candidates, target, i );
            path.removeLast();
            target+= candidates[i];
        }

    }
}

这里两个地方容易错:

  1. **target-=candidates[i]**的时候,如果我们回溯,这个时候target也需要回溯,所以需要加回去:target+= candidates[i];
  2. 之前因为不能重复,我们代码是这样的dfs(candidates, target, i+1 );这里改法也很简单,可以不+1,直接继续用i,会自己继续递归这一部分

这里也可以对for内的代码进行简单优化:

  1. 使用ArrayList加快速度,因为我们添加元素在尾部,所以使用ArrayList效率远远高于Deque
  2. 通过参数传递target,减少计算;可以带入数字理解,这里会更容易(其实就是一个是所有递归共享变量,而新的写法就是每一个递归一个target变量)
  3. 最后,因为已经减去过一次,只要找是否有满足(target - c[candidates])就可以
class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        dfs(candidates, target, 0);
        return res;
    }

    void dfs(int[] candidates, int target, int startIndex) {
        if (target < 0)
            return;

        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = startIndex; i < candidates.length; i++) {
            if (candidates[i] <= target) {
                path.add(candidates[i]);
                dfs(candidates, target - candidates[i], i);
                path.remove(path.size()-1); //回溯
            }
        }

    }
}

L131 分割回文串

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

示例 1:

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

示例 2:

输入:s = "a"
输出:[["a"]]

提示:

  • 1 <= s.length <= 16
  • s 仅由小写英文字母组成

拿到这道题需要先思考,如何回溯呢?

我们有两种方法:

  • 第一次分割一个,递归时再分割第二个,第二次分割两个,递归时再往后分割一个。。
  • 另一种是第一次分割一个,递归的时候分割两个。。

很明显,第二种无法构成回溯,所以我们继续第一个方法思路往下想

如果想不出来,递归条件我们先略过,我们先把这道题看为不是分割回文串,先看为分割所有可能的字符串就行

这样想就很简单了,只需要:

   List<List<String>> res = new ArrayList<>();
    List<String> path = new ArrayList<>();
public List<List<String>> partition(String s) {
        dfs(s, 0);
        return res;
    }

    void dfs(String s, int startIndex) {
        if (startIndex == s.length()) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = startIndex; i < s.length(); i++) {
          //startIndex就是我们开始的索引
             path.add(s.substring(startIndex, i + 1));
            
            dfs(s, i + 1);
            path.remove(path.size() - 1);
        }
    }

到这里其实已经完成了,我们将问题分解后,现在只需要考虑回文字符串,怎么判断呢?很简单,给定区间,写一个方法调用就行了,但是写这个方法为了保证速度,我们使用位运算降维打击:

完整代码:

class Solution {
    List<List<String>> res = new ArrayList<>();
    List<String> path = new ArrayList<>();

    public List<List<String>> partition(String s) {
        dfs(s, 0);
        return res;
    }

    void dfs(String s, int startIndex) {
        if (startIndex == s.length()) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = startIndex; i < s.length(); i++) {
            if (isPalindrome(s, startIndex, i)) {
                path.add(s.substring(startIndex, i + 1));
            } else {
                continue;
            }
            dfs(s, i + 1);
            path.remove(path.size() - 1);
        }
    }

    boolean isPalindrome(String s, int startIndex, int end) {
        for (int i = startIndex, j = end; i < j; i++, j--) {
            if ((s.charAt(i) ^ s.charAt(j)) != 0)
                return false;
        }
        return true;
    }
}

L78 子集

给你一个整数数组 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 中的所有元素 互不相同

这道题一开始的思路很简单,让我们想起来刚刚的那道L77

 public void dfs(int n, int k, int startIndex,List<Integer>path,List<List<Integer>>res){
        // 递归终止条件是:path 的长度等于 k
        if (path.size()== k){
            res.add(new ArrayList<>(path));
            return;
        }
        // 针对一个结点,遍历可能的搜索起点,其实就是枚举
        for (int i = startIndex;  i<=n ; i++) {
            path.add(i);
//            搜索起点要加1是为了缩小范围,下一轮递归做准备,因为不允许出现重复的元素
            dfs(n,k,i+1,path,res);
            path.remove(path.size()-1);
        }
    }

这里我们重新回来讨论:

image-20240419204052125

我们知道上面之所以会停下,是因为递归的结束条件设置的是:path.size()== k,也就是当我们找到满足数量要求k的组合,如果我们不限制k会怎么样呢?

例如:

public void dfs(int n, int k, int startIndex, List<Integer> path, List<List<Integer>> res) {
        // 递归终止条件是:path 的长度等于 k

        res.add(new ArrayList<>(path));

        // 针对一个结点,遍历可能的搜索起点,其实就是枚举
        for (int i = startIndex; i <= n; i++) {
            path.add(i);
            // 搜索起点要加1是为了缩小范围,下一轮递归做准备,因为不允许出现重复的元素
            dfs(n, k, i + 1, path, res);
            path.remove(path.size() - 1);
        }
    }

结果是:

[[],[1],[1,2],[1,2,3],[1,2,3,4],[1,2,4],[1,3],[1,3,4],[1,4],[2],[2,3],[2,3,4],[2,4],[3],[3,4],[4]]

本来我们觉得会报错,但是实际上for循环执行结束后,这个递归也会结束,简单理解就是我们整个执行流程其实就是每一个for的循环执行的时候,都不断分支出i-1个结果不断递归

明白这一点,我们来分析过程:

image-20240420172014219

这里我们发现,其实需要的结果就是过程中所有的结合,这里好解决,直接每一次递归的时候添加就好了,可是什么时候结束循环呢?因为startIndex >= nums.size(),本层for循环本来也结束了,和刚才上面的讲解一种情况,这里也不需要结束循环,只需要自己结束就好,完整代码:

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> subsets(int[] nums) {
        backTracking(nums, 0);
        return res;
    }

    void backTracking(int[] nums, int startIndex) {
        res.add(new ArrayList<>(path));
        for (int i = startIndex; i < nums.length; i++) {
            path.add(nums[i]);
            backTracking(nums, i + 1);
            path.remove(path.size() - 1);
        }
    }
}

这里我们也不需要考虑空集,因为第一次执行恰好包括了空集,当然这都是执行后来看了,有点巧合性

L46 全排列

给定一个不含重复数字的数组 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]]

提示:

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • nums 中的所有整数 互不相同

这道题我们只有{1,2,3}可能不好分析,可以在纸上多加几个数字分析可以更清晰

首先依然是回溯,但是第一次是1开头,第二次2…

也就是说我们只需要for不断从0开始,跳过需要跳过的就行,而结束条件也很简单,就是当path长度和nums长度一样,说明找到一组排列

但是这里有一个很重要的一点:我们用过的数字还能继续用,这里怎么解决呢?

这里我们把回溯过程画深一点发现,一直到底下,其实就是不断的枚举,只是跳过当前开头的那个数字就行

这里过程图:

image-20240420181239786

我们发现,取第几个,此时就需要从第几个的后面一个取新值,而且!回溯的时候需要把这里取过的值夜复原

这里的思路是定义一个数组,每次递归这个的时候,将设置为true,回溯后改为false

代码如下:

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] used;

    public List<List<Integer>> permute(int[] nums) {
        used = new boolean[nums.length];
        backTracking(nums);
        return res;
    }

    void backTracking(int[] nums) {
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) {
                continue;
            } else {
                path.add(nums[i]);
                used[i] = true;
                backTracking(nums);
                path.remove(path.size() - 1);
                used[i] = false;
            }
        }
    }
}

L784 字母大小写全排列

给定一个字符串 s ,通过将字符串 s 中的每个字母转变大小写,我们可以获得一个新的字符串。

返回 所有可能得到的字符串集合 。以 任意顺序 返回输出。

示例 1:

输入:s = "a1b2"
输出:["a1b2", "a1B2", "A1b2", "A1B2"]

示例 2:

输入: s = "3z4"
输出: ["3z4","3Z4"]

提示:

  • 1 <= s.length <= 12
  • s 由小写英文字母、大写英文字母和数字组成

这道题首先分析回溯过程:

了解了过程后,其实只需要把数字时直接跳过,遍历即可,这里结束条件依然是当pos为0的时候,但是这里需要注意,我们有两个递归:

  1. 保持当前状态的递归调用:
    • 这是基线的递归,即不改变当前字符的大小写状态。通过这种方式,我们可以探索在当前字母保持不变的情况下,字符串其余部分的所有可能组合。
  2. 改变大小写的递归调用:
    • 在这个递归调用中,我们改变当前字母的大小写状态(如果是小写则变为大写,反之亦然)。这允许我们探索在当前字母改变大小写的情况下,字符串其余部分的所有可能组合。

举例说明:

假设我们有字符串 s = "a1b2"。我们将分步地查看递归如何处理每个字符:

  1. Step 1: 处理 'a'
  • 选择1: 保持 'a',继续递归处理 "1b2"
  • 选择2: 改为 'A',继续递归处理 "1b2"
  1. Step 2: 遇到 '1'
  • 数字: 直接跳过,继续处理 "b2"
  1. Step 3: 处理 'b'

对于从 'a' 和 'A' 传递下来的每个字符串:

  • 选择1: 保持 'b',继续递归处理 "2"
  • 选择2: 改为 'B',继续递归处理 "2"
  1. Step 4: 遇到 '2'
  • 数字: 直接跳过,此时字符串已处理完毕,将结果添加到结果集中
  1. 结果集

通过上述递归处理,我们可以得到以下组合:

  • "a1b2"
  • "a1B2"
  • "A1b2"
  • "A1B2"

完整代码如下:

class Solution {
    List<String> res = new ArrayList<>();

    public List<String> letterCasePermutation(String s) {
        backTracking(s.toCharArray(), 0);
        return res;
    }

    void backTracking(char[] ch, int pos) {
        while (pos < ch.length && Character.isDigit(ch[pos])) {
            pos++;
        }
        if (pos==ch.length){
            res.add(new String(ch));
            return;
        }
        backTracking(ch,pos+1);
        ch[pos]^=32;
        backTracking(ch,pos+1);
        ch[pos]^=32;
    }

}

L79 单词搜索

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

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

示例 1:

img

输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出:true

示例 2:

img

输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出:true

示例 3:

img

输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出:false

提示:

  • m == board.length
  • n = board[i].length
  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • boardword 仅由大小写英文字母组成

思路:

分别遍历每一个点,找到一个合适的就在那个合适的四周寻找

false结束条件:

  1. 行或列索引越界
  2. 当前矩阵元素与目标字符不同
  3. 当前矩阵元素已访问过。

true结束:

k = len(word) - 1

知道这些其实就已经可以做出来了,但是第一次接触这种题会不知道怎么下手,其实很相似, boolean res的四个||条件则是四个方向,在这步前需要将board【i】【j】设置为空字符

class Solution {
    public boolean exist(char[][] board, String word) {
        char[] chars = word.toCharArray();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (backTracking(board, chars, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    boolean backTracking(char[][] board, char[] chars, int i, int j, int k) {
        if (i >= board.length || i < 0 || j >= board[0].length || j < 0 || chars[k] != board[i][j])
            return false;
        if (k == chars.length - 1)
            return true;
        board[i][j] = '\0';
        boolean res = backTracking(board, chars, i + 1, j, k + 1)
                || backTracking(board, chars, i - 1, j, k + 1)
                || backTracking(board, chars, i, j + 1, k + 1)
                || backTracking(board, chars, i, j - 1, k + 1);
        board[i][j] = chars[k];
        return res;
    }
}

L93 复原IP地址

有效 IP 地址 正好由四个整数(每个整数位于 0255 之间组成,且不能含有前导 0),整数之间用 '.' 分隔。

  • 例如:"0.1.2.201" "192.168.1.1"有效 IP 地址,但是 "0.011.255.245""192.168.1.312""192.168@1.1"无效 IP 地址。

给定一个只包含数字的字符串 s ,用以表示一个 IP 地址,返回所有可能的有效 IP 地址,这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

示例 1:

输入:s = "25525511135"
输出:["255.255.11.135","255.255.111.35"]

示例 2:

输入:s = "0000"
输出:["0.0.0.0"]

示例 3:

输入:s = "101023"
输出:["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

提示:

  • 1 <= s.length <= 20
  • s 仅由数字组成

首先解读题目:

  1. 不能有前导0:意思是当有一个0时,这段数字就结束了,需要下一段
  2. 组成的排列有两个要求:
    • 一个IP有四段数字,并且每一段使用.分割
    • 每一个数字的范围是0-255
  3. 给定的字符串按照要求分割成为有效的IP

这个时候就该分析回溯的过程了,首先我们看到分割IP和之前的分割回文串很相似,我们可以先分析过程:

假如:25525511135:

  1. 分割第一个2,分割第二个5,分割第三个5,这个时候很明显没有将所有的数字用到这样不合理,因此一个递归的截止条件便是此时截取出的长度等于给定的字符串长度

image-20240421220732003

这里因为我们每一个递归都需要对数字的有效性进行判断,就和之前的分割回文串一样,我们给定区间,判断这段的数字是否合法,因为给定的字符串只有数字,因此不需要判断合法性

  boolean isValid(String s, int start, int end) {
        if (start > end) return false;
        if (s.charAt(start) == '0' && start != end) return false;
        int sum = 0;
        for (int i = start; i <= end; i++) {
            sum = sum * 10 + (s.charAt(i) - '0');
        }
        if (sum > 255) return false;
        return true;
    }

有这个方法后,我们进行回溯部分代码的编写,因为IP地址只有四段,不是无限分割的,所以不能用切割线切到最后作为终止条件,而是分割的段数到了4就必须终止。

我们用变量pointNum来表示小数点数量,pointNum为3说明字符串分成了4段了。

完整代码如下:

class Solution {
    List<String> res = new ArrayList<>();

    public List<String> restoreIpAddresses(String s) {
        if (s.length() < 4 || s.length() > 12) {
            return res;
        }
        backTracking(s, 0, 0);
        return res;
    }

    void backTracking(String s, int startIndex, int pointNum) {
        if (pointNum == 3) {
            if (isValid(s, startIndex, s.length() - 1)) {
                res.add(s);
            }
            return;
        }
        for (int i = startIndex; i < s.length(); i++) {
            if (isValid(s, startIndex, i)) {
                s = s.substring(0, i + 1) + "." + s.substring(i + 1);
                pointNum++;
                backTracking(s, i + 2, pointNum);
                pointNum--;

                s = s.substring(0, i + 1) + s.substring(i + 2);

            } else {
                break;
            }
        }
    }

    boolean isValid(String s, int start, int end) {
        if (start > end)
            return false;
        if (s.charAt(start) == '0' && start != end)
            return false;
        int sum = 0;
        for (int i = start; i <= end; i++) {
            sum = sum * 10 + (s.charAt(i) - '0');
            if (sum > 255)
                return false;
        }

        return true;
    }
}

这道题有两个地方很难理解,这里debug调试一下

  1. 第一个枝点

首先我们来道第一个枝点,也就是startIndex=0的时候,我们这里深入:

这里因为上一步添加了小数点,所以这里i变成了2,到了第一个5

image-20240422113422251

然后一直再递归一次,小数点变成了3个,进行结束判断,最后一段数字不符合要求,结束:

image-20240422113708845

  1. 第二个枝点,同理,依然是最后一段数字不符合要求
  2. 一直到我们第一个成功结果,在第三个枝的时候,我们继续进行上述1,2操作,以此类推……

我们发现,回溯的根本就是暴力枚举+舍弃上一个结果

另一个细节就是,pointNum因为是所有递归都需要可见,所以直接定义变量

L17 电话号码的字母组合

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

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

img

示例 1:

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

示例 2:

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

示例 3:

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

提示:

  • 0 <= digits.length <= 4
  • digits[i] 是范围 ['2', '9'] 的一个数字。

首先分析题目:需要的结果就是 当给定两个数字:3*3=9,给定3个数字 3*3*3=27,而1没有字母,题目输入也不包括

到这里发现:给定数字的长度就是我们最后需要组合的长度,这道题只需要将数字转换为字母,其实就是一道排列组合问题,那么我们先处理映射关系:

key肯定是2-9,value我们设置为对应的字符串,这里我们优先使用自定义的数组与字符串,因为集合API会影响效率

    String[] kv = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

为了方便对应映射,我们空出两个空字符串加入数组,接下来分析回溯过程:

首先结果的数量是不变的,因此每一分支代表的分别是第一个数字的某一个字母,因此分支数量就清楚了,每个分支深入的话,依次是第2,3…个数字,结束条件便是当结果的长度到达给定数字长度即可

单看题目结束条件,这道题和46的全排列有点像,但是不同的是这道题的分支是给定数字对应的字母映射

那么最复杂的就是代码实现了,

  1. 首先想:我们每一层遍历都需要一个索引,一直索引到了输入字符长度就可以结束了,所以参数两个:index和字符串
  2. 接下里我们还需要考虑横向遍历,也就是遍历每一个字符串数组中的每一个字母,所以我们套用回溯模板

但是for遍历的是字符串的第index个吗?很明显不是,而是对应字符串下标中数字对应的字母,因为每一层都需要这样对每一个字符串中字母进行回溯,但是回溯前需要先添加第一个元素:sb.append(str.charAt(i));

想不明白我们可以先写第一次,比如第一次对第一个字符串的映射进行回溯,然后观察代码,当深入一层遍历的时候

  1. 接下里就是回溯传递的参数了,我们的横向广度只需要每一次有for迭代就行,递归我们只需要考虑深度,所以我们参数依然分别是backTracking(digits, index + 1);
  2. 结束条件也只需要不断深入的index达到条件就行,这样效率更高

完整的代码:

class Solution {
    String[] kv = new String[] { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
    List<String> res = new ArrayList<>();
    StringBuilder sb = new StringBuilder();

    public List<String> letterCombinations(String digits) {
        if(digits.length()==0)return res;
        backTracking(digits, 0);
        return res;
    }

    void backTracking(String digits, int index) {
        if (index == digits.length()) {
            res.add(sb.toString());
            return;
        }

        String str = kv[digits.charAt(index) - '0'];
        for (int i = 0; i < str.length(); i++) {
            sb.append(str.charAt(i));
            backTracking(digits, index + 1);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

回溯和递归就像一颗树,递归是根,是深度;而for就像叶,是广度

L22 括号生成问题

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

示例 1:

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

示例 2:

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

提示:

  • 1 <= n <= 8

拿到这道题首先分析有效括号的可能性,没有什么规律,越想越不知所措。。。

所以分析括号生成,左右括号什么时候可以获得?

观察题目给的示例,只要剩余左括号的数量大于0,就可以添加"(",例如"("、"(()"、”(()(“、”()((“都是可以的,因为我们只要再给加几个右括号就行,例如可以将其变成"()"、"(())"、”(()()“、”()(())“。

那添加右括号的要求呢?

结论是:序列中左括号的数量必须大于右括号的数量,例如上面的"("、"(()"、”(()(“、”()((“,都可以,但是如果")"、"())"、”)()(“、”()((“就不可以了,此时的情况都是右括号数量大于等于左括号。

所以我们可以得到两条结论:

  1. 只要剩余左括号的数量大于0,就可以添加"("。
  2. 序列中左括号的数量必须大于右括号的数量才可以添加"(",并且")"的剩余数量大于0。

过程图:

image-20240422131518414

通过图示,可以得到如下结论:

  • 当前左右括号都有大于 0 个可以使用的时候,才产生分支,否则就直接停止。
  • 产生左分支的时候,只看当前是否还有左括号可以使用;
  • 产生右分支的时候,除了要求还有右括号,还要求剩余右括号数量一定大于左括号的数量;
  • 在左边和右边剩余的括号数都等于 0 的时候结束。

整体来说,左括号可以不断使用,知道使用完毕当前给定括号数量,右括号必须要当前使用过的左括号大于右括号才能使用,否则无法构成有效括号

代码不难实现,关键是要理解过程和画出回溯过程分析

 void backTracking(int left,int right,int max){
        if (sb.length()==2*max){
            res.add(sb.toString());
            return;
        }
        //使用过左括号
        if (left<right){
            sb.append("(");
            backTracking(left-1,right,max);
            sb.deleteCharAt(sb.length()-1);
        }
        if (left>right){
            sb.append(")");
            backTracking(left,right,max);
            sb.deleteCharAt(sb.length()-1);
        }
    }