leetcode 78 subset

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
11
>[
>  [3],
>  [1],
>  [2],
>  [1,2,3],
>  [1,3],
>  [2,3],
>  [1,2],
>  []
>]
>

class  {
    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位去

leetcode 78 subset

近期文章

近期评论

标签

热门

文章归档

分类目录

功能