78. 子集

题目描述

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

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

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

解法一

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        //位运算，
         /**
         * 0001 A
         * 0010 B
         * 0011 AB
         * 0100 C
         * 0101 AC
         * 0110 BC
         * 0111 ABC
         * 1000 []
         */

        List<List<Integer>> result = new ArrayList<>();

        int size = 1 << nums.length;
        for(int i = 0; i < size; i++){
            
            List<Integer> item = new ArrayList<>();
            for(int j = 0; j < nums.length; j++){

                if( ((i >> j) & 1) == 1 ){
                    item.add(nums[j]);
                }
            }
            result.add(item);
        }
        


        return result;
    }

   
}

解法二

class Solution {
    
    List<List<Integer>> result = new ArrayList<>();
    
    public List<List<Integer>> subsets(int[] nums) {
        if(nums == null || nums.length == 0) return result;
        
        List<Integer> list = new ArrayList<Integer>();
        result.add(new ArrayList<>(list));   //添加空集
        
        generate(list,nums,0);
        
        return result;    
    }
    
    private void generate(List<Integer> list,int[] nums,int start){
        
        for(int i = start; i < nums.length; i++){
            list.add(nums[i]);
            result.add(new ArrayList<>(list));
            generate(list,nums,i+1);
            list.remove(list.size() -1);
        }
    }
}

解法三

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        //回溯法,每个数字出现或者不出现
        //[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

        List<List<Integer>> result = new ArrayList<>();

        List<Integer> item = new ArrayList<>(); //添加空集
        result.add(new ArrayList<Integer>(item));   //添加到result的时候需要复制集合，因为Java保存的是引用

        generate(0, nums, item, result);
        return result;
    }

    private void generate(int i, int[] nums, List<Integer> item, List<List<Integer>> result) {
        if (i >= nums.length) return;

        item.add(nums[i]);
        result.add(new ArrayList<Integer>(item));   //出现
        generate(i + 1, nums, item, result);

        item.remove(item.size() - 1);   //不出现
        generate(i + 1, nums, item, result);
    }
}