文章目录

Leetcode Leetcode 78- 子集

Leetcode Leetcode 78- 子集

1. 题目描述

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

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

输入: 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	[],[1],[2],[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实现

import java.util.*;

/**
 * @ClassName Subset
 * @Deacription // TODO
 * @Author LiuZhian
 * @Date 2019-11-10 09:43
 * @Version 1.0
 **/

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;
        }

        // 其他nums个数大于1时
        // 取最后一个作为anotherItem
        int anotherItem = nums[nums.length - 1];
        int[] subNums = Arrays.copyOfRange(nums, 0, nums.length - 1);
        res = setComination(subNums, subsets(subNums), anotherItem);

        return res;
    }

    // 在基于nums的所有子集基础上，再加上一个anotherItem得到的所有集合
    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) {
            // 用ls初始化tmpList
            List<Integer> tmpList = new ArrayList<>(ls);
            // 再添加anotherItem
            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实现

//  位运算
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. 类似题

LeetCode90-子集②
4.1 迭代思路

这个题和本题（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.即：两个集合中的元素数量相等，且对应元素均相等。

//  位运算
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);
}

Leetcode 78- 子集

Naive V.S. 牛掰格拉斯