LeetCode

Appearance

90. Subsets II ​

题目 ​

Given an integer array nums that may contain duplicates, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

 

Example 1:

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

Example 2:

Input: nums = [0]
Output: [[],[0]]

 

Constraints:

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10
Related Topics
  • 位运算
  • 数组
  • 回溯

  • 👍 1312
  • 👎 0

    • 思路 ​

    求解组合方式，设计 backtrack 函数时需要记下 start 作为起始位置

    • 由于求组合方式，遍历完整个数组后即结束了整个寻找，故也不需要额外添加结束条件
    • 重复元素，需要将数组先排序，当遍历的节点和前一个遍历的节点重复时可以跳过该节点

    解法 ​

    py
    # leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()

        def backtrack(start, path):
            res.append(path[:])
            for i in range(start, len(nums)):
                if i > start and nums[i] == nums[i - 1]:
                    continue
                path.append(nums[i])
                backtrack(i + 1, path)
                path.pop()


        backtrack(0, [])
        return res
        
# leetcode submit region end(Prohibit modification and deletion)

    复杂度分析 ​

    • 时间复杂度 O(2n)
    • 空间复杂度 O(n)