回溯---集合的子集 Posted on 2021-07-05 00:00:00 2021-07-05 00:00:00 by Author 摘要 高中时我们学过集合，找一个集合的子集是非常简单的事情，那么用程序实现这个事情该怎么弄尼？一起看看吧！！！！！！ # 回溯---集合的子集 1. 题目描述 - 给你一个整数数组 `nums` ，数组中的元素 **互不相同** 。返回该数组所有可能的子集（幂集）。解集 **不能** 包含重复的子集。你可以按 **任意顺序** 返回解集。 2. 示例描述 - 示例一 - 输入：nums = [1,2,3] - 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] - 示例二 - 输入：nums = [0] - 输出：[[],[0]] - 示例三 - 输入：nums =[1,2] - 输出：[[],[1],[2],[1,2]] 3. 解题思路 - 本题又是一道经典的递归回溯算法题目，求子集问题就是相当于组合问题，无非就是集合中的元素相互之间组合，最后所有的元素相互组合完成后构成的结果就是一个集合的子集。 - 这里实现的方式还是套用我自己总结的递归五步法。首先递归出口的条件就是，集合中的每个元素与集合其他元素都相互组合完后，那么本个元素的递归也就结束了。第二步就是确定递归集合了，这里不难看出，本次递归的集合就是包含本节点和本节点之后的所有节点，为什么递归的集合不是整个数组集合尼，因为在递归遍历本节点之前，该节点之前的节点已经与其他节点相互组合了，如果本节点递归循环时的集合是整个数组，那么最后的结果集合中回出现重复的组合，到时候还要去重，所以这里的集合选取就是为了避免最终结果集合中出现相同的组合。第三步就是记录本层递归时的值，即就是记录本次循环当前节点的值。第四步就是继续递归寻找本节点下其他的与本节点相互组合的节点。最后一步就是该节点下层节点递归完成后，回退到当前递归的位置时，要回退到在执行本节点之前的状态，因为本节点是在一个集合中，为了保证集合中其他节点进行递归时初始状态不受影响，所以本节点要回退到初始状态。这样整个流程就完成。 - 其实自己掌握了递归回溯算法的套路后，遇到一个算法题，按照自己的套路去实现，也还挺简单，主要就是理解递归回溯的整个流程，理解之后以后做这种题目就会信手捏来的，下面是本道题的具体实现。 4. 具体实现 ```java //最终结果的集合 List<List<Integer>> result = new ArrayList<>(); public void trackBacking(int index, List<Integer> re, int[] nums) { //递归条件的出口，即每个节点与其他节点结合完毕后 //那么本节点的与其他节点组成的子集也就找完了。 if (index >= nums.length) { return; } //只要还满足条件，就向最终结果集合中加入本节点与其他节点的所有子集 result.add(new ArrayList<>(re)); //集合中每个元素都与其他节点相互组合，所以用遍历 //而遍历初始值不从0开始，就是为了去重 for (int i = index; i < nums.length; i++) { //满足条件就把该节点加入临时组合中， re.add(nums[i]); //继续寻找本节点与其他节点相互结合的子集 trackBacking(i + 1, re, nums); //回到当前节点递归前的初始状态 re.remove(re.size() - 1); } } ```
{{ item.content }}
{{ child.content }}