78.Subsets

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)O(nlogn)

็ป“ๆžœๆ•ฐไธบ 2n2^n ไธช๏ผŒๆ‰€ไปฅๆ—ถ้—ดๅคๆ‚ๅบฆไธบ: O(2n)O(2^n)

ไฝฟ็”จไธดๆ—ถๆ•ฐ็ป„listไฟๅญ˜ไธญ้—ด็ป“ๆžœ๏ผŒๆ‰€ไปฅ็ฉบ้—ดๅคๆ‚ๅบฆไธบ O(n)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;
  }
}

Last updated