【算法系列篇】递归、搜索和回溯（四）

文章目录

• 前言
• 什么是决策树
• 1. 全排列
• • 1.1 题目要求
  • 1.2 做题思路
  • 1.3 代码实现
  • 2. 子集
  • • 2.1 题目要求
    • 2.2 做题思路
    • 2.3 代码实现
    • 3. 找出所有子集的异或总和再求和
    • • 3.1 题目要求
      • 3.2 做题思路
      • 3.3 代码实现
      • 4. 全排列II
      • • 4.1 题目要求
        • 4.2 做题思路
        • 4.3 代码实现

          前言

          前面我们通过几个题目基本了解了解决递归类问题的基本思路和步骤，相信大家对于递归多多少少有了更加深入的了解。那么本篇文章我将为大家分享结合决策树来解决递归、搜索和回溯相关的问题。

          什么是决策树

          决策树是一种基本的分类与回归方法。在分类问题中，决策树通过构建一棵树形图来对数据进行分类。树的每个节点表示一个特征属性，每个分支代表一个特征属性上的判断条件，每个叶节点代表一个类别。在回归问题中，决策树可以预测一个实数值。

          下面是一个简单的决策树：

          

          知道了什么是决策树，下面我们将运用决策树来解决实际问题。

          
          （图片来源网络，侵删）

          1. 全排列

          https://leetcode.cn/problems/permutations/

          1.1 题目要求

          给定一个不含重复数字的数组 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 
              public List
              }
          }
          
              List
                  //对全局变量进行初始化
                  path = new ArrayList
              	//当path中元素的大小等于数组的大小，就说明一种情况已经列举完成，这事需要我们将当前path中的数据添加进ret中，并且返回
                  if (path.size() == nums.length) {
                      ret.add(new ArrayList
                     if (vis[i] == false) {
                         path.add(nums[i]);
                         //将当前元素标记为已使用
                         vis[i] = true;
                         //考虑该位置之后的其他元素的选择
                         dfs(nums);
                         //恢复现场
                         path.remove(path.size() - 1);
                         vis[i] = false;
                     }
                 }
              }
          }
          
              public List
              }
          }
          
              List
                  path = new ArrayList
                  //进入这个函数就可以将path中的结果添加进ret中，这样就可以将空集的情况给考虑上
                  ret.add(new ArrayList
                      path.add(nums[i]);
                      dfs(nums, i + 1);
                      path.remove(path.size() - 1);
                  }
              }
          }
          
              public int subsetXORSum(int[] nums) {
              }
          }
          
              int path;
              int ret;
              public int subsetXORSum(int[] nums) {
                  dfs(nums, 0);
                  return ret;
              }
              private void dfs(int[] nums, int pos) {
                  //前面是将集合添加进ret中，这里我们是将每种情况加进ret中
                  ret += path;
                  for (int i = pos; i