leetcode-回溯问题总结（DFS）

比眉伴天荒 2023-03-13 06:18 10阅读 0赞

### 文章目录 ###

*  1.DFS
 *  2. for+递归解决通用问题
 *  3. 回溯问题减枝加速
 *  4. 组合&排序&子集
 *   *  组合总和(回溯)（深度优先遍历DFS）
     *  组合总和2(剪枝)
     *  全排列（回溯）
     *  全排列2（剪枝）
     *  78.子集(回溯)

# 1.DFS #

图论里邻接表的DFS

private void dfs(boolean[] isVisited, int i) {  
            //将结点设置为已经访问
            isVisited[i] = true;
            //查找结点i的第一个邻接结点w
            int w = getFirstNeighbor(i);
            while(w != -1) { //说明存在当前临界点
                if(!isVisited[w]) { 
                    dfs(isVisited, w);
                }
                //如果w结点已经被访问过 获取下一个
                w = getNextNeighbor(i, w);
            }
    
        }

问题是：DFS只是找到一条路径就结束了，那么当我们解决回溯遍历的时候，这样的是不可取的

# 2. for+递归解决通用问题 #

力扣上有人总结出了回溯问题框架:

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

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

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

public void backtrack(路径，选择列表){ 
        if(满足结束条件){ 
            result.add(结果);
        }
        for(选择：选择列表){ 
            做出选择;
            backtrack(路径，选择列表);
            撤销选择;
        }
    }

例子:  
解数独问题：

> 判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
> 
> 数字 1-9 在每一行只能出现一次。  
> 数字 1-9 在每一列只能出现一次。  
> 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

> 解决思路:(建立已存在索引)  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70]  
> 黑色是初始，红色是需要填入的数字  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70 1]  
> [图来自][Link 1]

1.读入初始化的数独表

for (int i = 0; i < 9; ++i) { 
                for (int j = 0; j < 9; ++j) { 
                    if (board[i][j] != '.') { 
                        row[i][board[i][j] - '1'] = 1;
                        col[j][board[i][j] - '1'] = 1;
                        l[i / 3 * 3 + j / 3][board[i][j] - '1'] = 1;
                    }
                }
            }

1.  回溯填入可行数字

backtrace(board,0,0);

public boolean backtrace(char[][] board, int r, int c) { 
            //递归边界
            if (r > 8) return true;
            if (board[r][c] == '.') { 
                for (char ch = '1'; ch <= '9'; ++ch) { 
                    //符合要求 
                    if (row[r][ch - '1'] == 1 || col[c][ch - '1'] == 1 || l[r / 3 * 3 + c / 3][ch - '1'] == 1) continue;
                    //记录约束条件表
                    board[r][c] = ch;
                    row[r][ch - '1'] = 1;
                    col[c][ch - '1'] = 1;
                    l[r / 3 * 3 + c / 3][ch - '1'] = 1;
    
                    //递归查找下一个格子
                    if (backtrace(board, r + (c + 1) / 9, (c + 1) % 9)) return true;
    
                    // 如果没有找到可行数字，回溯 
                    board[r][c] = '.';
                    row[r][ch - '1'] = 0;
                    col[c][ch - '1'] = 0;
                    l[r / 3 * 3 + c / 3][ch - '1'] = 0;
                }
            } else return backtrace(board, r + (c + 1) / 9, (c + 1) % 9);//当前格子不为空，递归下一个格子
            //对空格处操作：没有得到合适的解就会跳到此处
            return false;
        }

这种回溯属于暴力解决的一种

# 3. 回溯问题减枝加速 #

> 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。  
> candidates 中的数字可以无限制重复被选取。  
> 说明：  
> 所有数字（包括 target）都是正整数。  
> 解集不能包含重复的组合。  
> 示例 1:  
> 输入: candidates = \[2,3,6,7\], target = 7,  
> 所求解集为:  
> \[  
> \[7\],  
> \[2,2,3\]  
> \]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70 2]  
[图片来自][Link 2]

去重：

if (i > index && candidates[i] == candidates[i - 1]) continue;

剪枝：

if (candidates[i] > target) break;

完整代码:

private List<List<Integer>> ans = new ArrayList<List<Integer>>();
    
        public List<List<Integer>> combinationSum2(int[] candidates, int target) { 
            Arrays.sort(candidates);
            backtrace(candidates, 0, target, new ArrayList<Integer>());
            return ans;
        }
    
        public void backtrace(int[] candidates, int index, int target, List<Integer> path) { 
            if (target == 0) ans.add(new ArrayList<>(path));
            for (int i = index; i < candidates.length; i++) { 
                // 去重
                if (i > index && candidates[i] == candidates[i - 1]) continue;
                //减枝
                if (candidates[i] > target) break;
    
                path.add(candidates[i]);
    
                backtrace(candidates, i + 1, target - candidates[i], path);
                path.remove(path.size() - 1);
            }
        }
    
        public static void main(String[] args) { 
            int[] ints = { 10, 1, 2, 7, 6, 1, 5};
            List<List<Integer>> sum2 = new q40_CombinationSum2().combinationSum2(ints, 8);
            System.out.println(sum2.toString());
        }

# 4. 组合&排序&子集 #

## 组合总和(回溯)（深度优先遍历DFS） ##

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

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

说明：

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

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

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

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

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

LinkedList result = new LinkedList();
    public void backtrack(路径，选择列表){
        if(满足结束条件){
            result.add(结果);
        }
        for(选择：选择列表){
            做出选择;
            backtrack(路径，选择列表);
            撤销选择;
        }
    }

[参考链接][Link 3]

private List<List<Integer>> ans = new ArrayList<List<Integer>>();
        public  List<List<Integer>> combinationSum(int[] candidates, int target) { 
            LinkedList<Integer> track = new LinkedList<>();
            Arrays.sort(candidates);
            backtrack(candidates, 0, target, track);
            return ans;
        }
    
        private  void backtrack(int[] candidates, int start, int target, 		    LinkedList<Integer> track) { 
            if (target < 0) return;
            if (target == 0){ 
                ans.add(new LinkedList<>(track));
                return;
            }
            for(int i = start;i < candidates.length;i++){ 
                if(target < candidates[i]) break;
                track.add(candidates[i]);
                backtrack(candidates,i,target-candidates[i],track);
                track.removeLast();
            }
        }

## 组合总和2(剪枝) ##

给定一个数组 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\]  
\]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70 3]

## 全排列（回溯） ##

> 给定一个 没有重复 数字的序列，返回其所有可能的全排列。  
> 示例:  
> 输入: \[1,2,3\]  
> 输出:  
> \[  
> \[1,2,3\],  
> \[1,3,2\],  
> \[2,1,3\],  
> \[2,3,1\],  
> \[3,1,2\],  
> \[3,2,1\]  
> \]

这个问题比较难以处理的就是，剩余待选项的处理

public void backtrack(int n,
                              ArrayList<Integer> output,
                              List<List<Integer>> res,
                              int first) { 
            // 所有数都填完了
            if (first == n)
                res.add(new ArrayList<Integer>(output));
            for (int i = first; i < n; i++) { 
                // 动态维护数组
                Collections.swap(output, first, i);
                // 继续递归填下一个数
                backtrack(n, output, res, first + 1);
                // 撤销操作
                Collections.swap(output, first, i);
            }
        }
    
        public List<List<Integer>> permuteByLeetcode(int[] nums) { 
            List<List<Integer>> res = new LinkedList();
    
            ArrayList<Integer> output = new ArrayList<Integer>();
            for (int num : nums)
                output.add(num);
    
            int n = nums.length;
            backtrack(n, output, res, 0);
            return res;
        }

[cangkao][]

## 全排列2（剪枝） ##

[参考][Link 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70 4]

public List<List<Integer>> permuteUnique(int[] nums) { 
            int len = nums.length;
            List<List<Integer>> res = new ArrayList<>();
            if (len == 0) { 
                return res;
            }
    
            // 排序（升序或者降序都可以），排序是剪枝的前提
            Arrays.sort(nums);
    
            boolean[] used = new boolean[len];
            // 使用 Deque 是 Java 官方 Stack 类的建议
            Deque<Integer> path = new ArrayDeque<>(len);
            dfs(nums, len, 0, used, path, res);
            return res;
        }
    
        private void dfs(int[] nums, int len, int depth, boolean[] used, Deque<Integer> path, List<List<Integer>> res) { 
            if (depth == len) { 
                res.add(new ArrayList<>(path));
                return;
            }
    
            for (int i = 0; i < len; ++i) { 
                if (used[i]) { 
                    continue;
                }
    
                // 剪枝条件：i > 0 是为了保证 nums[i - 1] 有意义
                // 写 !used[i - 1] 是因为 nums[i - 1] 在深度优先遍历的过程中刚刚被撤销选择
                if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) { 
                    continue;
                }
    
                path.addLast(nums[i]);
                used[i] = true;
    
                dfs(nums, len, depth + 1, used, path, res);
                // 回溯部分的代码，和 dfs 之前的代码是对称的
                used[i] = false;
                path.removeLast();
            }
        }

## 78.子集(回溯) ##

> 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
> 
> 说明：解集不能包含重复的子集。  
> 示例:  
> 输入: nums = \[1,2,3\]  
> 输出:  
> \[  
> \[3\],  
> \[1\],  
> \[2\],  
> \[1,2,3\],  
> \[1,3\],  
> \[2,3\],  
> \[1,2\],  
> \[\]  
> \]

List<List<Integer>> ans = new ArrayList<List<Integer>>();
        LinkedList<Integer> path = new LinkedList();
        public List<List<Integer>> subsets(int[] nums) { 
    
            if (nums.length == 0) return ans;
            backtrace(nums, 0);
    
            return ans;
        }
    
        private void backtrace(int[] nums, int i) { 
            ans.add(new ArrayList<>(path));//空集
            for (int j = i; j < nums.length ; j++) { 
                path.add(nums[j]);
                backtrace(nums, j + 1);
                path.removeLast();
            }
        }

递归处理：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70 5]

public List<List<Integer>> subsets(int[] nums) { 
        List<List<Integer>> output = new ArrayList();
        output.add(new ArrayList<Integer>());
    
        for (int num : nums) { 
          List<List<Integer>> newSubsets = new ArrayList();
          for (List<Integer> curr : output) { 
            newSubsets.add(new ArrayList<Integer>(curr){ { add(num);}});
          }
          for (List<Integer> curr : newSubsets) { 
            output.add(curr);
          }
        }
        return output;
    
      }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70]: /images/20230312/82e45db686554a4f82557ef87c65b1e4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70 1]: /images/20230312/6e40b250abc94ddab74dbc3dbddb8a51.png
[Link 1]: https://leetcode-cn.com/problems/sudoku-solver/solution/jie-shu-du-by-leetcode/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70 2]: /images/20230312/ebfd380fe1ff41e1a512aa82fa625f35.png
[Link 2]: https://leetcode-cn.com/problems/combination-sum-ii/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-3/
[Link 3]: https://leetcode-cn.com/problems/combination-sum/solution/java-dfsrang-ni-zhi-dao-zu-he-zen-yao-qu-zhong-jia/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70 3]: /images/20230312/bce7e643142d4f89839d439c46e99bdc.png
[cangkao]: https://leetcode-cn.com/problems/permutations/solution/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liweiw/
[Link 4]: https://leetcode-cn.com/problems/permutations-ii/solution/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liwe-2/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70 4]: /images/20230312/94d8297a37ff4d1f8eedef42312c06a8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70 5]: /images/20230312/235119521c694611970cfefefcbf8c79.png