140 - 90 子集2

题目

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

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

示例:

输入: [1,2,2] 输出: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]

解答

和子集1一样，在插入到res的时候做个判断就行了

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

        def helper(level, temp):
            res.append(temp)
            for i in range(level, len(nums)):
                if i > level and nums[i] == nums[i-1]:
                    continue
                helper(i+1, temp+[nums[i]])

        helper(0, [])
        return res

Runtime: 36 ms, faster than 97.11% of Python3 online submissions for Subsets II.

Memory Usage: 12.9 MB, less than 100.00% of Python3 online submissions for Subsets II.

var subsetsWithDup = function(nums) {
  const ans = []
  nums.sort()
  const helper = function(level, temp) {
    ans.push(temp)
    for (let i = level; i < nums.length; i++) {
      if (i > level && nums[i] === nums[i - 1]) {
        continue
      }
      const next = temp.slice()
      next.push(nums[i])
      helper(i + 1, next)
    }
  }
  helper(0, [])
  return ans
};

if dRuntime: 56 ms, faster than 97.29% of JavaScript online submissions for Subsets II.

Memory Usage: 35.6 MB, less than 60.00% of JavaScript online submissions for Subsets II.

func subsetsWithDup(nums []int) [][]int {
    ans := make([][]int, 0)
    sort.Ints(nums)
    var helper func(int, []int)
    helper = func(level int, temp []int) {
        ans = append(ans, temp)
        for i := level; i < len(nums); i++ {
            if i > level && nums[i] == nums[i-1] {
                continue
            }
            next := make([]int, len(temp))
            copy(next, temp)
            next = append(next, nums[i])
            helper(i+1, next)
        }
    }
    helper(0, []int{})
    return ans
}

Runtime: 4 ms, faster than 81.58% of Go online submissions for Subsets II.

Memory Usage: 6.9 MB, less than 100.00% of Go online submissions for Subsets II.