leetcode算法-子集-78

2024-06-13 07:58

文章标签 leetcode 算法子集 78

本文主要是介绍leetcode算法-子集-78，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

leetcode算法-子集

leetcode传送门

题目

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

解题思路

本题是用来求一个集合的幂集,也就是说将集合各个元素进行排列组合，返回所有组合。
我的做法是使用动态规划的思想,自底向上求解。
首先我们可以发现幂集有一个性质,一个集合的子集的幂集一定包含于该集合的幂集，在上面的例子中就是[1,2,3]的幂集一定包含[2,3]的幂集。那么除了子集的幂集之外呢。
[2,3]的幂集为[[2],[3],[2,3],[]],而[1,2,3]比[2,3]的幂集多出的幂集为[1,2],[1,3],[1,2,3],[1],有没有发现什么呢?

很容易发现,集合[1,2,3]的比集合[2,3]多出来的幂集正好是集合[1,2,3]比集合[2,3]多的元素1与集合[2,3]的幂集逐一进行并集运算之后的结果。

于是解法也就浮出水面:
求任意一个集合A的幂集Sa,其中a是集合A中的一个元素,我们可以先求出集合A去除a的子集B的幂集Sb,然后将集合Sb添加到Sa中,之后遍历Sb,将Sb中的每个元素添加一个元素a,最后将添加结束之后的Sa添加到Sb中即可得出集合A的幂集。
那么子集B的幂集怎么求呢？递归调用重复上述步骤即可。直到最后只剩下一个元素的集合，我们便可直接得到该单元素集合的幂集。

代码

class Solution {public List<List<Integer>> subsets(int[] nums) {if(nums==null||nums.length==0)return new ArrayList<>();return sub(nums, 0);}public static List<List<Integer>> sub(int[] nums,int start) {List<List<Integer>> resultList = new ArrayList<List<Integer>>();if(start==nums.length-1) {List<Integer> list = new ArrayList<>();list.add(nums[start]);resultList.add(list);list = new ArrayList<>();resultList.add(list);return resultList;}else {List<List<Integer>> list2 = sub(nums, start+1);resultList.addAll(list2);List<Integer> tmpList = null;for (List<Integer> list3 : list2) {tmpList = new ArrayList<>(list3);tmpList.add(nums[start]);resultList.add(tmpList);}}return resultList;}
}