位操作 - 求子集[M]

题目

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],
  []
]

思路

1. 利用bitmap

这是一个非常巧妙的思路，因为对于子集来说，每个元素只有2种状态：在子集中，不在子集中

这刚好符合2进制，可以考虑使用bitmap的方法。

我们对每个元素一个bit：

• 0：在当前子集中

• 1：不在当前子集中

对于n个元素，一共有2^n种取法，这和子集数也是一致的。

拿2个元素{1,2}举例：

• 00 ——> [] //1不取，2不取

• 01 ——> [1] //取1

• 10 ——> [2] //取2

• 11 ——> [1,2] //取1，2

刚好可以取尽所有元素。

这个算法的复杂度是O(N^2)，一层循环从0到2^n种取法，二层循环看每个取法对应的2进制中的1的个数

代码

public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> mylist = new ArrayList<List<Integer>>();
        int len = 1<<nums.length;
        //System.out.println(len);
        for(int i = 0;i < len;i++)
        {
            List<Integer> tmplist = new ArrayList<Integer>();
            for(int j = 0;j < nums.length;j++)
            {
                if(((1<<j) & i) != 0)
                {
                    tmplist.add(nums[j]);
                }
            }
            mylist.add(tmplist);
        }
        return mylist;
    }
}

递归，回溯

用回溯法，因为是子集，[1,2]和[2,1]一样，所以我们的每次递归的停止条件都是到nums[]中的最后一个元素。

代码

public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
            List<List<Integer>> mylist = new ArrayList<List<Integer>>();
            getsubset(mylist,0,nums,new ArrayList<Integer>());
            return mylist;
        }
        private void getsubset(List<List<Integer>> mylist, int cur, int[] nums, List<Integer> tmplist){
            mylist.add(tmplist);
            for(;cur < nums.length;cur++) {
                List<Integer> newlist = new ArrayList<Integer>(tmplist);
                newlist.add(nums[cur]);
                getsubset(mylist, cur + 1,nums,newlist);
            }
        }
}