LeetCode78

题目链接https://leetcode-cn.com/problems/subsets/submissions/

题目：

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

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

示例:

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

//方法1：二进制法

class Solution {

    public List<List<Integer>> subsets(int[] nums) {

        int all_set = 1 << nums.length;

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

        for(int i = 0; i < all_set; i++){

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

            for(int j = 0; j < nums.length; j++){

                if(((i >> j) & 1) != 0){

                    tmp.add(nums[j]);

                }

            }

            result.add(tmp);

        }

        return result;

    }

}

//方法2：回溯法

class Solution {

    public List<List<Integer>> subsets(int[] nums) {

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

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

        int step = 0;

        generate(step, nums, tmp, result);

        return result;

    }

    public void generate(int step, int[] nums, List<Integer> tmp, List<List<Integer>> result){

        result.add(new ArrayList<>(tmp));

        for(int i = step; i < nums.length; i++){

            tmp.add(nums[i]);

            generate(i+1, nums, tmp, result);

            tmp.remove(tmp.size()-1);

        }

    }

}