P116 数组的子集

描述#

这个题目说的是，给你一个不包含重复元素的整数数组，你要返回它所有可能的子集。

比如说，给你的数组是：
1, 2, 4
[1, 2, 4] 这三个数字可以形成的子集数量是 2^3 = 8 个：
(),
(1),
(2),
(4),
(1, 2),
(1, 4),
(2, 4),
(1, 2, 4)

代码#

public class AlgoCasts {

  private void subsets(int[] nums, int start,
                       List<Integer> elem, List<List<Integer>> result) {
    result.add(new ArrayList<>(elem));
    for (int i = start; i < nums.length; ++i) {
      elem.add(nums[i]);
      subsets(nums, i + 1, elem, result);
      elem.remove(elem.size() - 1);
    }
  }

  // Time: O(2^n), Space: O(n)
  public List<List<Integer>> subsetsRecursive(int[] nums) {
    if (nums == null || nums.length == 0) return new ArrayList<>();
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> elem = new ArrayList<>();
    subsets(nums, 0, elem, result);
    return result;
  }

  // Time: O(n*2^n), Space: O(1)
  public List<List<Integer>> subsetsBit(int[] nums) {
    if (nums == null || nums.length == 0) return new ArrayList<>();
    List<List<Integer>> result = new ArrayList<>();
    int n = nums.length;
    int N = (int)Math.pow(2, n);

    for (int i = 0; i < N; ++i) {
      List<Integer> elem = new ArrayList<>();
      for (int j = 0; j < n; ++j)
        if (((i >> j) & 1) == 1)
          elem.add(nums[j]);
      result.add(elem);
    }
    return result;
  }

}