LeetCode-面试题08-04-幂集

2020-06-02

题目描述

幂集。编写一种方法，返回某集合的所有子集。集合中不包含重复的元素。

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

示例：

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

思路

nums = [1,2,3]，长度为3，幂集的大小为2^nums.length-1。
根据nums，将1表示取，0表示不取，则有

[0,0,0] -> 0 -> []
[0,0,1] -> 1 -> [3]
[0,1,0] -> 2 -> [2]
[0,1,1] -> 3 -> [2,3]
[1,0,0] -> 4 -> [1]
[1,0,1] -> 5 -> [1,3]
[1,1,0] -> 6 -> [1,2]
[1,1,1] -> 7 -> [1,2,3]

0和1就分别对应0-7这8种中的二进制。

代码

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>(); //结果
        int n = 1 << nums.length;   //得到nums的子集个数
        //循环n
        for(int i=0;i<n;i++){
            int m = i;  
            int index = 0;  //指向nums的元素
            List<Integer> temp = new ArrayList<>();
            //遍历二进制m的每一位
            while(m != 0){
                //若m当前位是1，则表示取当前位的元素
                if((m & 1) != 0){
                    temp.add(nums[index]);
                }
                m = m >> 1; //m右移一位
                index++;    //下标++
            }
            result.add(temp);
        }
        return result;
    }
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/power-set-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。