打印数组的所有子集

打印数组的所有子集

作者:Grey

原文地址:

博客园:打印数组的所有子集

CSDN:打印数组的所有子集

无重复值情况

题目描述见: LeetCode 78. Subsets

主要思路

定义递归函数

void p(int[] arr, int i, LinkedList<Integer> pre, List<List<Integer>> result) 

递归含义是:数组arri往后开始收集所有的子集,i之前生成的子集是pre,所有生成的子集都存在result中,

base case 就是,当i来到arr.length位置的时候,此时,已经没有选的字符了,将收集到的pre加入result中,

针对普遍情况,可能性有两种,第一种,不要选择i位置的元素,那么接下来直接调用p(arr, i + 1, pre, result)

第二种情况,选择i位置的元素,则将i位置的元素加入pre的下一个位置中,即:pre.addLast(arr[i]),然后去下一个位置做决策,即p(arr, i + 1, pre, result)

第二种情况中,不要忘记选择了i位置的元素,在后续决策完毕后,需要恢复现场,即pre.removeLast()

完整代码见

class Solution {     public static List<List<Integer>> subsets(int[] nums) {         List<List<Integer>> result = new ArrayList<>();         p(nums, 0, new LinkedList<>(), result);         return result;     }      // i往后收集所有的子集     public static void p(int[] arr, int i, LinkedList<Integer> pre, List<List<Integer>> result) {         if (i == arr.length) {             List<Integer> ans = new ArrayList<>(pre);             result.add(ans);         } else {             // 不要i位置             p(arr, i + 1, pre, result);             pre.addLast(arr[i]);             // 要i位置             p(arr, i + 1, pre, result);             // 恢复现场             pre.removeLast();         }     } } 

有重复值情况

题目描述见: LeetCode 90. Subsets II

上一个问题由于题目限定了,没有重复元素,所以处理相对简单一些,本题说明了输入参数中可能会有重复的元素,且生成的子集不能有重复,此时有两个思路:

第一个思路,基于上一个问题的结果,即result,做去重操作,思路比较简单,但是复杂度会相对高一些,因为我们每次都要全量得到所有的子集,然后最后才去重。

第二个思路,在执行递归函数的时候,可以做一些剪枝,无须到最后再来去重,直接在递归函数中就把结果生成出来。接下来讲第二个解法的思路。

由于题目中已经说明,返回子集的顺序无要求,那么,我们可以首先将数组进行排序,排序后,所有相同的元素一定会排列到一起,然后定义一个和上一题一样的递归函数

void p(int[] nums, int i, LinkedList<Integer> pre, List<List<Integer>> result) 

递归含义是:数组arri往后开始收集所有的无重复子集,i之前生成的子集是pre,所有生成的子集都存在result中。

接下来分析递归函数的可能性,我们可以不要选择i位置的元素,那么则可以直接加入result.add(new ArrayList<>(pre)),按上一题逻辑,接下来我们应该去i+1位置收集结果,但是,由于有重复元素,所以接下来ii+1,……i + n 都有可能是同一个元素,示例图如下

打印数组的所有子集

如上图,i一直到i+n都是元素a,直到i+n+1才是一个不同的元素,所以,当我们收集了i位置的元素以后,我们不能直接去i+1位置收集,而是应该从i+n+1位置开始收集。

完整代码见

class Solution {     public static List<List<Integer>> subsetsWithDup(int[] nums) {         List<List<Integer>> lists = new ArrayList<>();         Arrays.sort(nums);         p(nums, 0, new LinkedList<>(), lists);         return lists;     }      public static void p(int[] nums, int i, LinkedList<Integer> pre, List<List<Integer>> result) {         result.add(new ArrayList<>(pre));         for (int s = i; s < nums.length; s++) {             // 一直到下一个不等于s位置元素的地方             if (s > i && nums[s] == nums[s - 1]) {                 continue;             }             pre.add(nums[s]);             p(nums, s + 1, pre, result);             pre.remove(pre.size() - 1);         }     } } 

更多

算法和数据结构笔记

发表评论

相关文章