leetcode: Subsets

问题描述：

Given a set of distinct integers, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

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

 

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

原问题链接：https://leetcode.com/problems/subsets/

 

问题分析

　　关于集合生成的问题在之前的文章里有过详细的讨论。相对来说它的解法也有若干种，其中最简洁的一种要数二进制法了。这种思路就是基于给定的数组来说，假设它的长度为n。那么它里面所有元素的所有可能被选择的情况是2 ** n。那么我们可以定义一个值为2 ** n的数字，从0开始一直到这个数字，每个数字对应它里面元素的一种选择情况。这样这个数字对应的二进制位里面为0的表示未选取的，为1的表示选取的。每取一个数字这么选取一次元素。最终可以得到所有选取的情况。

　　在详细的实现里，问题的细节点在于判断一个数字里面的为1的位，我们采取1 << j来表示数字1左移j位。通过它和给定的数字逐位的与运算来计算结果。如果这个结果不为0，则对应数组里nums[j]的元素被选取。

　　详细的代码实现如下：

 

public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new LinkedList<>();
        for(int i = 0; i < 1 << nums.length; i++) {
            List<Integer> list = new LinkedList<>();
            for(int j = 0; j < nums.length; j++) {
                if((i & (1 << j)) != 0) list.add(nums[j]);
            }
            result.add(list);
        }
        return result;
    }
}