78.subsets

发表评论
379 views

 ›
78.subsets

78. 子集

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

输入: nums = [1,2,3]
输出:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

解法一

分治

  1. 需要 revere states
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        if(nums == null) return ans;
        dfs(ans, nums, new ArrayList<>(), 0);
        return ans;
    }

    public void dfs(List<List<Integer>> ans, int[] nums, List<Integer> list, int index) {

        // terminator
        if (index == nums.length) {
            ans.add(new ArrayList<Integer>(list));
            return;
        }

        dfs(ans, nums, list, index + 1); // not pick the number at this index

        list.add(nums[index]); 
        dfs(ans, nums, new ArrayList<>(list), index + 1); // pick the number at this index

        // restore state
        list.remove(list.size() - 1);
    }
}
  1. 直接传递拷贝, 不需要 reverse states
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        if(nums == null) return ans;
        dfs(ans, nums, new ArrayList<>(), 0);
        return ans;
    }

    public void dfs(List<List<Integer>> ans, int[] nums, List<Integer> list, int index) {

        // terminator
        if (index == nums.length) {
            ans.add(new ArrayList<Integer>(list));
            return;
        }

        dfs(ans, nums, list, index + 1); // not pick the number at this index

        List<Integer> curList = new ArrayList<>(list);
        curList.add(nums[index]);
        dfs(ans, nums, curList, index + 1); // pick the number at this index
    }
}

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
      result = []
      if nums == None:
        return result
      self.dfs(result, nums, [], 0)
      return result

    def dfs(self, result, nums, arr, index):
      # terminator
      if index == len(nums):
        result.append(arr.copy())
        return

      self.dfs(result, nums, arr, index+1) # not pick the number at this index
      arr.append(nums[index])
      self.dfs(result, nums, arr, index+1) # pick the number at this index

      # restore state
      arr.pop()

class Solution:
  def subsets(self, nums: List[int]) -> List[List[int]]:
    self.res = []
    self.dfs(nums, [], 0)
    return self.res

  def dfs(self, nums, temp, index):
    self.res.append(temp[:]) # self.res.append(temp.copy)
    for i in range(index, len(nums)):
      temp.append(nums[i])
      self.dfs(nums, temp, i+1)
      temp.pop()

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []

        def helper(i, tmp):
            res.append(tmp)
            for j in range(i, len(nums)):
                helper(j + 1, tmp + [nums[j]])
        helper(0, [])
        return res

解法二

迭代

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        subsets = [[]]

        for num in nums:
            newsets = []
            for subset in subsets:
                new_subset = subset + [num]
                newsets.append(new_subset)
            subsets.extend(newsets)

        return subsets

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = [[]]

        for num in nums:
            res = res + [[num] + n for n in res]
        return res