78.Subsets.md

78. Subsets

---

题目地址

https://leetcode.com/problems/subsets/

http://www.lintcode.com/en/problem/subsets/

题目描述

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: nums = [1,2,3]
Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

代码

Approach #1 DFS

数组排序的算法复杂度 $$O(nlogn)$$

结果数为 $$2^n$$ 个，所以时间复杂度为: $$O(2^n)$$

使用临时数组list保存中间结果，所以空间复杂度为 $$O(n)$$

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    if (nums == null || nums.length == 0) return result;

    // dfs
    List<Integer> list = new ArrayList<Integer>();
    dfs(nums, 0, list, result);

    return result;
  }

  private void dfs(int[] nums, int pos, List<Integer> list, List<List<Integer>> ret) {
    // Put it first,  let's make it have an empty set
    ret.add(new ArrayList<Integer>(list));

    for (int i = pos; i < nums.length; i++) {
      list.add(nums[i]);
      dfs(nums, i + 1, list, ret);
      list.remove(list.size() - 1);
    }
  }

}

Approach 2: Recursion

class Solution {
  public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> output = new ArrayList();
    output.add(new ArrayList<Integer>());
    
    for (int num: nums) {
      List<List<Integer>> newSubsets = new ArrayList();
      for (List<Integer> curr: output) {
        newSubsets.add(new ArrayList<Integer>(curr){{add(num);}});
      }
      for (List<Integer> curr: newSubsets) {
        output.add(curr);
      }
    }
    return output;
  }
}