Subsets

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

Note:
Elements in a subset must be in non-descending order.
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],
  []
]

求子集问题，最直接的办法是用回溯法，假设一共有n个元素，子集的个数为2^n个，找出长度length从0到n的所有的可能的组合，回溯的条件根据当前的length来决定。代码如下：

public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        LinkedList<Integer> list = new LinkedList<Integer>();
        List<List<Integer>> llist = new LinkedList<List<Integer>>();
        if(nums == null || nums.length == 0) return llist;
        java.util.Arrays.sort(nums);
        for(int lth = 0; lth <= nums.length; lth++) {
            getSubsets(0, lth, nums, list, llist);
        }
        return llist;
    }
    public void getSubsets(int start, int lth, int[] nums, LinkedList<Integer> list, List<List<Integer>> llist) {
        if(list.size() == lth) {
            llist.add(new LinkedList<Integer>(list));
            return;
        }
        for(int i = start; i < nums.length; i++) {
            list.add(nums[i]);
            getSubsets(i + 1, lth, nums, list, llist);
            list.removeLast();
        }
    }
}

还有一种很巧妙的方法，用位运算的方法来解决。长度为n的数组num[]，它的子集的个数为2^n个，假设第i个子集，我们如何用位运算得到它呢？我们可以将i依次右移0到n次，每次都与1位与，如果结果为1，假设位移了k位，那么就把数组中第k个元素nums[k]加入结果中。这样正好可以找到数组中所有的子集。代码如下：

public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<Integer> list;
        List<List<Integer>> llist = new ArrayList<List<Integer>>();
        if(nums == null || nums.length == 0) return llist;
        java.util.Arrays.sort(nums);
        for(int i = 0; i < Math.pow(2, nums.length); i++) {
            list = new ArrayList<Integer>();
            for(int j = 0; j < nums.length; j++) {
                if((i >> j & 1) == 1)
                    list.add(nums[j]);
            }
            llist.add(list);
        }
        return llist;
    }
}