78. Subsets (Medium) Facebook Amazon Bloomberg Uber

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:

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

Solution 1: DFS O(n * 2^n); O(n)

    /**
     * DFS O(n*2^n);O(n)
     * [[],[1],[1,2],[1,2,3], start从0到2
     * [1,3],
     * [2],[2,3],
     * [3]]
     * Add current subset to result first.
     * Put current number in subset.
     * Then backtrack with the rest of the numbers.
     * Reset by remove last number in subset.
     * Next iteration will move to next number then all subsets will not have this number.
     */
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null) {
            return res;
        }

        //找到所有以[]开头的子集
        dfs(res, new ArrayList<>(), nums, 0);
        return res;
    }

    //找到所有以subset开头的子集
    //从nums[start]开始选择数，术语offset
    private void dfs(List<List<Integer>> res, List<Integer> subset, int[] nums, int start) {
        res.add(new ArrayList<>(subset));
        for (int i = start; i < nums.length; i++) {
            subset.add(nums[i]);
            dfs(res, subset, nums, i + 1);
            subset.remove(subset.size() - 1);
        }
    }

Solution 2: BFS O(n * 2^n); O(n)

    /**
     * BFS O(n*2^n);O(n)
     * [[],[1],
     * [2],[1,2],
     * [3],[1,3],[2,3],[1,2,3]]
     */
    public List<List<Integer>> subsetsB(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null) {
            return res;
        }

        res.add(new ArrayList<>());
        for (int i = 0; i < nums.length; i++) {
            int size = res.size();
            for (int j = 0; j < size; j++) {
                List<Integer> subset = new ArrayList<>(res.get(j));
                subset.add(nums[i]);
                res.add(subset);
            }
        }
        return res;
    }

Solution 3: BFS + Bit Manipulation O(n * 2^n); O(n)

    public List<List<Integer>> subsetsC(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        if (nums == null) {
            return list;
        }
//        if (nums.length == 0) {
//            list.add(new ArrayList<>());
//            return list;
//        }

        int totalNumber = 1 << nums.length;
        for (int i = 0; i < totalNumber; i++) {
            List<Integer> tempList = new ArrayList<>();
            for (int j = 0; j < nums.length; j++) {
                if ((i & (1 << j)) != 0) {
                    tempList.add(nums[j]);
                }
            }
            list.add(tempList);
        }
        return list;
    }