Leetcode Leetcode 78- 子集
1. 题目描述
给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。
说明:解集不能包含重复的子集。
1 2 3 4 5 6 7 8 9 10 11 12
| 输入: nums = [1,2,3] 输出: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
|
2. 思路
2.1 我的思路
依然先手动列举,我开始也没想到怎么做。先列出1,2,3的所有子集,为:
1
| [],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]
|
这时好像还没发现什么规律,我再列举4个元素1,2,3,4的情况,为:
1 2
| [],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3] [4],[1,4],[2,4],[3,4],[1,2,4],[1,3,4],[2,3,4],[1,2,3,4]
|
诶,等会儿,好像有了,不就是之前1,2,3的子集,每个再加上一个4吗?为了验证是否的确是这样,我又列举了1,2的情况,为:
再改写一下1,2,3的情况下所有子集的排列顺序
1 2
| [],[1],[2],[1,2] [3],[1,3],[2,3],[1,2,3]
|
是的,就是这样递归求解。所以思路就是:先找nums[0~len-2]的所有子集,再在暂时得到所有子集中添加一个nums[len-1]。
我把代码大致写了一下,的确能AC,就是内存消耗会略微有点大。
2.2 别人牛掰的思路
作者:yi-qu-xin-ci
链接:https://leetcode-cn.com/problems/subsets/solution/wei-yun-suan-by-yi-qu-xin-ci/
来源:力扣(LeetCode)
我们知道,对于给定一个集合里,所有元素的集合它们应该满足这样一个公式: 假设所有的组合数之和为sum,则有sum = C(n, 0) + C(n, 1) + …+ C(n, n); 分别对应取集合中的一个元素,两个元素…n个元素。而通过数学公式二项式定义,这个和是等于2 ** n(2的n次方)。就是说,我们所有取的组合数为一个指数函数。
假设输入是1、2、3。
首先全部的子集为【000】【001】【010】【100】【011】【101】【110】【111】
1表示这一位的数字存在,例如 【010】 表示只含有 2
由此发现子集所代表的二进制数全部小于 1 << 数组.length
第一层循环for (int i = 0; i < (1 << size); i++)
然后根据【i】
的二进制数中 【1】
的位置取得子集
3. 代码
3.1 迭代思路Java实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62
| import java.util.*;
public class Subset78 {
public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> res = new ArrayList<>(); if (nums.length == 0) return res; if (nums.length == 1) { List<Integer> empty = new ArrayList<>(); res.add(empty); for (int i = 0; i < nums.length; i++) { List<Integer> tmpList = new ArrayList<>(); tmpList.add(nums[i]); res.add(tmpList); } return res; }
int anotherItem = nums[nums.length - 1]; int[] subNums = Arrays.copyOfRange(nums, 0, nums.length - 1); res = setComination(subNums, subsets(subNums), anotherItem);
return res; }
private List<List<Integer>> setComination(int[] nums, List<List<Integer>> alreadyCal, int anotherItem) { List<List<Integer>> res = new ArrayList<>(alreadyCal.size() * 2); res.addAll(alreadyCal);
for (List<Integer> ls : alreadyCal) { List<Integer> tmpList = new ArrayList<>(ls); tmpList.add(anotherItem); res.add(tmpList); } return res; }
public static void main(String[] args) { int[] nums = {1, 2, 3}; Subset78 s = new Subset78(); List<List<Integer>> res = s.subsets(nums); for (List<Integer> ls : res) { System.out.println(ls.toString()); } } }
|
3.2 位运算思路Java实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| public List<List<Integer>> subsetsBitOps(int[] nums) { List<List<Integer>> res=new ArrayList<>(); int len = nums.length; for (int i = 0; (i < 1 << len); i++) { List<Integer> tmpList = new ArrayList<>(); for (int j = 0; j < len; j++) { if ( ( (1 << j) & i) != 0) { tmpList.add(nums[j]); } } res.add(tmpList); } return res; }
|
4. 类似题
这个题和本题(78题)的区别是,数组中元素可能存在重复。
看了一下评论区的题解,有一个刚好是对我之前想的迭代思想的延续
主要的思路就是在每次添加新的列表时,必须是在上次新解的基础上添加。具体的描述详见:https://leetcode-cn.com/problems/subsets-ii/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-19/
4.2 位操作思路
其实位操作思路倒是很简单,就是如果直接按照二进制位的情况去重还是有点麻烦。我想到了一个简单粗暴的方法,效率不是那么高,但也能AC。
既然你会重复,那我就让你重复好了,我用一个集合(这里用的是TreeSet),自定义集合比较大小方法,其实我们只要写好了集合相等时的比较就Ok.即:两个集合中的元素数量相等,且对应元素均相等。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
| // 位运算 public List<List<Integer>> subsetsWithDupBitOps(int[] nums) { Set<List<Integer>> s = new TreeSet<>(new Comparator<List<Integer>>() { @Override public int compare(List<Integer> o1, List<Integer> o2) { if (o1.size() < o2.size()) return -1; else if (o1.size() > o2.size()) return 1; Collections.sort(o1); Collections.sort(o2); Iterator<Integer> iter1 = o1.iterator(); Iterator<Integer> iter2 = o2.iterator(); while (iter1.hasNext() && iter2.hasNext()) { int i1 = iter1.next(); int i2 = iter2.next(); if (i1 < i2) return -1; else if (i1 > i2) return 1; } return 0; } }); int len = nums.length; for (int i = 0; (i < 1 << len); i++) { List<Integer> tmpList = new ArrayList<>(); for (int j = 0; j < len; j++) { if (((1 << j) & i) != 0) { tmpList.add(nums[j]); } } s.add(tmpList); } return new ArrayList<>(s); }
|