题目

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);

            }

        }

}

results matching ""

    No results matching ""