題目鏈接https://leetcode-cn.com/problems/subsets/submissions/

題目：

給定一組不含重復(fù)元素的整數(shù)數(shù)組nums，返回該數(shù)組所有可能的子集（冪集）。

說(shuō)明：解集不能包含重復(fù)的子集。

示例:

輸入:nums = [1,2,3]輸出:[? [3],? [1],? [2],? [1,2,3],? [1,3],? [2,3],? [1,2],? []

//方法1：二進(jìn)制法

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

? ? ? ? }

? ? }

}