标签： 回溯

n 位格雷码序列 是一个由 2n 个整数组成的序列，其中：

• 每个整数都在范围 [0, 2n - 1] 内（含 0 和 2n - 1）
• 第一个整数是 0
• 一个整数在序列中出现 不超过一次
• 每对 相邻 整数的二进制表示 恰好一位不同 ，且
• 第一个 和 最后一个 整数的二进制表示 恰好一位不同

给你一个整数 n ，返回任一有效的 n 位格雷码序列 。

 

示例 1：

输入：n = 2
输出：[0,1,3,2]
解释：
[0,1,3,2] 的二进制表示是 [00,01,11,10] 。
- 00 和 01 有一位不同
- 01 和 11 有一位不同
- 11 和 10 有一位不同
- 10 和 00 有一位不同
[0,2,3,1] 也是一个有效的格雷码序列，其二进制表示是 [00,10,11,01] 。
- 00 和 10 有一位不同
- 10 和 11 有一位不同
- 11 和 01 有一位不同
- 01 和 00 有一位不同

示例 2：

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

 

提示：

• 1 <= n <= 16

找规律想方法，找到对称关系

试着先从头开始写几行数据看下吧

   0
   0    1
  00   01   11   10
 000  001  011  010  110  111  101  100
0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000

1. 只有0的时候，不明显，继续往下看，只有第二行也一样
2. 第三行，我们先把数字都扩充到2位，之前的变成00, 01，那么剩下的只有11, 10 了此时只有 00 01 11 10这个顺序了，其他的组合情况暂不考虑
3. 第三行依旧扩充到3位000 001 011 010 ，下一个数字要和010只有一位不同的话只能选择110了，再下一位依旧只能111，这样 101 100
4. 开始总结规律，可以看到后半部分都是1xx这样的数据了，且如果户管最高位的话，和前面的内容是对称的，即，下标i和下标n - i对应，且下标i的值加1xx(二进制数)等于下标n - i 的值，那么我们基本就总结出规律了
5. 看第四行，原本前8位数字整体原封不动的保留，同时对应后面对称位置的值为当前位置的值加1000(二进制数)

稍微总结下

这个怎么来理解关系呢？我们来缕下 假设数组长度为 2n，（n不等于0，指实际位置从1开始，不是指从0开始的下标）

1. 从对称的最中间两位开始看，也就是第 n和n+1位，这两个数字后面部分是完全一样的，只有头部第一位一个是1 一个是0的区别，相差一位
2. 再看n-1 和n+2这两个对称位置，拿上面的第四行数据中间部分来说明
   0101 0100 1100 1101
   对应数字为0101和 1101, 因为0101和后面一位0100相差一位，所以同样对称部分的1100和1101如果忽略头部的1的话和这边其实是一致的也是相差一位，而又因为这两者头部都是加的1是相同的，所以这两者是必然相差一位的即n+1与n+2相差的一位是和n-1与n相差的一位是一样的
3. 再往后更多的对称部分和这一步也一样可以推断出是相差一位的

代码

class Solution {
    public List<Integer> grayCode(int n) {
        int i = 0;
        int[] list1 = new int[1];
        int[] list2 = new int[2];
        while (++i <=n){
            list2 = new int[1<<i];
            int lastIdx = list1.length * 2 - 1;
            int plus = 1 << (i-1);
            for (int idx = 0; idx < list1.length; idx++) {
                list2[idx] = list1[idx];
                list2[lastIdx - idx] =  list1[idx] | plus ;
            }
            list1 = list2;
        }
        List<Integer> r = new ArrayList<>();
        for (int i1 : list2) {
            r.add(i1);
        }
        return r;
    }
}

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

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

 

例如，在下面的 3×4 的矩阵中包含单词 “ABCCED”（单词中的字母已标出）。

示例 1：

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

示例 2：

输入：board = [["a","b"],["c","d"]], word = "abcd"
输出：false

 

提示：

• 1 <= board.length <= 200
• 1 <= board[i].length <= 200
• board 和 word 仅由大小写英文字母组成

 

注意：本题与主站 79 题相同：https://leetcode-cn.com/problems/word-search/

回溯模板题了已经相当

回溯模板题了已经相当于。

1. 找一个开头匹配的
2. 往四个方向开始匹配下一个字符
3. 中途标记已经访问过的节点
4. 退出递归的时候记得要把访问过的节点标记为未访问过

class Solution {
    boolean[][] visited;

    char[][] board;

    int[][] dist = {{1,0},{-1,0},{0,1},{0,-1}};

    public boolean exist(char[][] board, String word) {
        visited = new boolean[board.length][board[0].length];
        this.board = board;

        for (int row = 0; row < board.length; row++) {
            for (int col = 0; col < board[row].length; col++) {
                if (board[row][col] == word.charAt(0) && searchWord(word,0, row, col)){
                    return true;
                }
            }
        }
        return false;
    }

    boolean searchWord(String word, int idx, int row,int col){
        if (idx == word.length()-1 && word.charAt(idx) == board[row][col]){
            return true;
        }
        if (word.charAt(idx) != board[row][col]){
            return false;
        }
        visited[row][col] = true;

        for (int[] ints : dist) {

            int x = row + ints[0];
            int y = col + ints[1];
            if ( x<0 || y<0 || x >= board.length || y >= board[0].length || visited[x][y] ){
                continue;
            }

            if (searchWord(word,idx+1,x,y)){
                return true;
            }
        }
        visited[row][col] = false;
        return false;
    }
}

给定一个 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

 

提示：

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

 

进阶：你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？

标准回溯题

1. 挨个遍历找首字母匹配
2. 从匹配的首字母开始往四个方向遍历匹配下一个字母，并记录已访问过的点坐标
3. 遍历的过程中如果有字母不匹配返回false
4. 遍历的过程中判断越界情况和已访问过的情况
5. 直到匹配到最后一个字符完全相同 返回false
6. 退出递归记得改掉已访问过的坐标为false

class Solution {

    char[][] board;
    int[][] target = {{1,0},{0,1},{-1,0},{0,-1}};
    String word;

    public boolean exist(char[][] board, String word) {
        this.board = board;
        this.word = word;
        boolean[][] visited = new boolean[board.length][board[0].length];
        for (int row = 0; row < board.length; row++) {
            for (int col = 0; col < board[0].length; col++) {
                visited[row][col] = true;
                if (board[row][col] == word.charAt(0) && dfs(row,col, visited, 0)){
                    return true;
                }
                visited[row][col] = false;
            }
        }
        return false;
    }



    private boolean dfs(int row, int col, boolean[][] visited, int idx){
        if (idx== word.length()-1 && word.charAt(idx)==board[row][col]){
            return true;
        }

        if (word.charAt(idx) != board[row][col]){
            return false;
        }
        for (int[] ints : target) {
            int nextRow = row+ints[0];
            int nextCol = col+ints[1];
            if (nextRow>= board.length || nextRow < 0 || nextCol >= board[0].length || nextCol < 0 || visited[nextRow][nextCol]){
                continue;
            }
            visited[nextRow][nextCol] = true;
            if (dfs(nextRow,nextCol, visited,idx+1)){
                return true;
            }
            visited[nextRow][nextCol] = false;
        }
        return false;
    }
}

给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。

返回所有可能的结果。答案可以按 任意顺序 返回。

 

示例 1：

输入：s = "()())()"
输出：["(())()","()()()"]

示例 2：

输入：s = "(a)())()"
输出：["(a())()","(a)()()"]

示例 3：

输入：s = ")("
输出：[""]

 

提示：

• 1 <= s.length <= 25
• s 由小写英文字母以及括号 '(' 和 ')' 组成
• s 中至多含 20 个括号

类似广度优先搜索的处理办法、JAVA（详细注释）

括号字符串匹配问题我们常用的一个方法，遇到‘（’加1，遇到‘）’减1，结果为0的时候能表示形成完美匹配闭合。
这个问题也可以类比的想象为出入栈问题，‘（’入栈，‘）’出栈
另外，括号运算也可以类比的换算为其他结构，比如“树”
这是一个非常有意思的话题，不过题归正传，回到我们这题上

一顿分析

自己搞个字符串分析下看看，第二行标记的对应的映射关系，第三行统计了求和的值

 (  (  )  (  )  )  )  )  (  )  )  (  (  (  )
 1  1 -1  1 -1 -1 -1 -1  1 -1 -1  1  1  1  -1
 1  2  1  2  1  0 -1

当我们遇到这个和为-1的时候，很明显的说明了( ( ) ( ) ) )这段中有多余的)了，那么我们就把这段中的多余的)删掉一个再继续处理，可以得到如下两段，其中有一种连续的) )的情况删除任何一个结果都是一样的，这个可以再优化一下。

 (  (  )  (  )  ) 
 (  (  (  )  )  ) 

取第一种情况继续分析，那么字符串就变成了

 (  (  )  (  )  )  )  (  )  )  (  (  (  )
 1  1 -1  1 -1 -1 -1  1 -1  -1 1  1  1  -1
 1  2  1  2  1  0 -1 

再次遇到了-1继续同样的操作，在所有的结果中我们再取其中一种，以下省略数步，得到其中一个如下结果

 (  (  )  (  )  )  (  )  (  (  (  )
 1  2  1  2  1  0  1  0  1  2  3  2

最终的结果为2，这是另外一种情况，对应的我们应该往前删除两个(，但是前面的(很多，我们应该删除哪两个呢？

显然这个不能随意删除任意的(了，而是只能删除最后出现结果为0往后的位置中的(，但是这里面也有很多个(，又要删除哪两个呢？

最直观的办法当然是枚举所有的可能性，但是额外再写个枚举组合的算法好像有点麻烦，那么我们不如每个位置的(都删除一下，生成对应个数的字符串，然后再次处理整个逻辑，直到最后多余的(都处理掉的情况。

当然这里也直观的可以看到了重复( (的时候其实删除任意一个都是一样的，这个也许可以再优化一点点。

那么整个逻辑都清楚了，下面看代码，已经加了一点点额外的剪枝优化，

1. maxSize记录了已经得到的结果的最长长度，如果新的字符串比这个短就不用再处理了
2. history记录了已经处理过的字符串的哈希表，如果已经处理过了就不用再处理这个了
3. res结果先存入这个哈希表中，直接去重，防止有重复的结果被统计

代码

class Solution {

    HashSet<String> history = new HashSet<>();
    HashSet<String> res = new HashSet<>();
    public List<String> removeInvalidParentheses(String s) {
        Queue<String> queue = new LinkedList<>();
        //加入一个队列待处理
        queue.offer(s);
        //maxSize 记录下当前得到的符合预期的结果中最长的结果的长度
        int maxSize = 0;
        while (!queue.isEmpty()){
            String currentStr = queue.poll();
            if (currentStr.length()<maxSize){
                //如果这个字符串的长度已经小于可行结果中的最大长度，那么说明再处理之后得到的结果也不是最少删减个数能得到的
                continue;
            }
            //下标标记
            int idx = -1;
            //遇到"("加1，遇到")"减1 遍历到idx位置的时候得到的结果
            int total = 0;
            //最有一个total等于0的时候的位置，后面有多余的"("的时候要用到
            int lastZero = -1;
            //判断是否遇到了total=-1的情况，其实也可以在下面修改flag = false;的地方用跳出外面一层循环的写法
            boolean flag = true;
            while (++idx < currentStr.length() && flag){
                if (currentStr.charAt(idx) == '('){
                    //遇到'('加1
                    total++;
                }
                if (currentStr.charAt(idx) == ')'){
                    ////遇到'('减1，其他都不用管
                    total--;
                }
                if (total==0){
                    //等于0的时候记录下最后0出现的位置
                    lastZero = idx;
                }
                //当到达某个下标的时候total=-1了，说明')'多了一个，需要在前面的所有')'中删除掉一个
                if (total==-1){
                    //标记遇到-1的情况了
                    flag = false;
                    for (int i = 0; i <= idx; i++) {
                        //从头开始找')'
                        if (currentStr.charAt(i)==')'){
                            //删除掉指定位置的')'，生成新字符串
                            String tmpStr = strDeleteIndex(currentStr,i);
                            //如果没有处理过这种字符串的话，把他加入到queue、并标记为已经处理过这种的
                            if (!history.contains(tmpStr)){
                                history.add(tmpStr);
                                queue.add(tmpStr);
                            }
                        }
                    }
                }
            }
            //如果没有遇到total=-1的情况，说明这里已经遍历到字符串的结尾了
            if (flag){
                //最终位置结果如果是大于0的，说明前面的lastZero位置到结束位置之间有多余的'('
                if (total > 0){
                    //需要往前遍历找到最后一个0的位置lastZero从里面删除total个"("左括号，但是n个'('里面选total个'（'不是太好处理，需要组合不同情况
                    //那么我们就换一个简单点的办法，每个'('都删除一下，生成一个字符串，并重新执行上面的之前的逻辑，即把删除了一个'('的字符串
                    //重新加进queue再处理一遍，每次处理一个'('，直到最终处理掉了所有多余的'('
                    int i = lastZero;
                    while (++i < currentStr.length()){
                        if (currentStr.charAt(i) == '('){
                            //和上面处理')'一样，删除当前位置的'('，并加入到queue再次处理
                            String tmpStr = strDeleteIndex(currentStr,i);
                            if (!history.contains(tmpStr)){
                                history.add(tmpStr);
                                queue.add(tmpStr);
                            }
                        }
                    }
                }else if (total == 0 && currentStr.length() >= maxSize){
                    //正好能闭合的添加进结果集，
                    //另外再判断更新maxSize，如果是长度比已有结果短的字符串就不用处理了
                    maxSize = currentStr.length();
                    res.add(currentStr);
                }
            }
        }
        List<String> l = new ArrayList<>();
        int finalMaxSize = maxSize;
        res.forEach(str->{
            if (str.length()== finalMaxSize){
                //再判断一遍长度，这边我也不确定是不是需要，所以保险起见还是写下吧
                l.add(str);
            }
        });
        return l;
    }


    /**
     * 删除字符串指定下标位置的字符的封装方法，返回一个新的删除了指定位置的字符的字符串
     * 由于调用的地方已经严格控制的idx不会越界，所以idx的越界问题就没有做判断处理
     * @param str 原始字符串
     * @param idx 待删除位置下标
     * @return 新的删除了指定位置字符的字符串
     */
    public String strDeleteIndex (String str, int idx){
        char[] arr = new char[str.length()-1];
        char[] origin = str.toCharArray();
        System.arraycopy(origin,0,arr,0,idx);
        System.arraycopy(origin,idx+1,arr,idx,arr.length-idx);
        return new String(arr);
    }
}

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

 

示例 1：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]

示例 2：

输入：root = [1,2,3], targetSum = 5
输出：[]

示例 3：

输入：root = [1,2], targetSum = 0
输出：[]

 

提示：

• 树中节点总数在范围 [0, 5000] 内
• -1000 <= Node.val <= 1000
• -1000 <= targetSum <= 1000

注意：本题与主站 113 题相同：https://leetcode-cn.com/problems/path-sum-ii/

回溯DFS

深度优先搜索回溯的一般应用题。
相对的有一个比较类似但又不一样的题目可以结合起来一起学习理解【图解说明】DFS回溯+前缀和

不同的是在437. 路径总和 III是求的路径上的区间合，需要借助前缀和的概念来处理。

本题分析
从根节点开始，往下DFS遍历，并记录路基上的节点合 和 节点的List集合
当是根节点的时候，判断路径合是不是等于目标值，如果是把节点List集合塞进返回结果集里
在退出当前节点遍历的时候，需要清除List集合中当前节点的值
代码

class Solution {

    List<List<Integer>> res = new ArrayList<>();
    int target;
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        if (null == root){
            return new ArrayList<>();
        }
        this.target = target;
        dfs(root,0,new ArrayList<>());
        return res;
    }


    public void dfs(TreeNode node, int sum, List<Integer> list){
        if (node==null){
            return;
        }
        list.add(node.val);
        if (node.left == null && node.right == null){
            if (sum + node.val == target){
                res.add(new ArrayList<>(list));
            }
            list.remove(list.size()-1);
            return;
        }
        dfs(node.left, sum + node.val,list);
        dfs(node.right,sum + node.val,list);
        list.remove(list.size()-1);
    }
}

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

简单

就DFS，在叶子节点的时候，即没有左右子节点的时候，判断这个链路上的和是否等于targetSum，如果等于则把之前记录的path加入到list集合中，此处需要复制一份出来。
并再退出的时候重新减去当前node的val，

class Solution {
    List<List<Integer>> list = new ArrayList<>();
    int sum = 0;
    int targetSum = 0;
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        this.targetSum = targetSum;
        dfs(root,new ArrayList<>());
        return list;
    }

    public void dfs(TreeNode node, List<Integer> path){
        if (node==null){
            return;
        }
        sum += node.val;
        path.add(node.val);
        if (node.left == null && node.right == null && sum == targetSum){
            list.add(new ArrayList<>(path));
        }
        dfs(node.left, path);
        dfs(node.right, path);
        path.remove(path.size()-1);
        sum -=node.val;
    }
}