leetcode 78 Subset
z
 2018-03-05 17:09:08  

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,3], a solution is:

1
2
3
4
5
6
7
8
9
10
>[
 [3],
 [1],
 [2],
 [1,2,3],
 [1,3],
 [2,3],
 [1,2],
 []
>]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        int total = 1 << nums.length;
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        for(int i=0; i<total; i++){
            ArrayList<Integer> t = new ArrayList<Integer>();
            for(int j=0; j<nums.length; j++){
                if(((i>>j)&1) == 1){
                    t.add(nums[j]);
                }
            }
            ans.add(t);
        }
        return ans;
    }
}
  • 用位操作来实现
  • 1 << nums.length 为ans的数目。即2^nums.length
  • (i>>j & 1) 用来判断第i为是否要取
    • eg. i = 4，即 i：0100
      • i>>0 & 1 ==0 表示第0位不取
      • i>>1 & 1 == 0 表示第1位不取
      • i>>2 & 1 == 1 表示第2位去