90.subsets-ii

Statement

简体中文English

Metadata

• Link: 子集 II
• Difficulty: Medium
• Tag: 位运算 数组 回溯

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

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

 

示例 1：

输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

 

提示：

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10

Metadata

• Link: Subsets II
• Difficulty: Medium
• Tag: Bit Manipulation Array Backtracking

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

Solution

Python 3

from typing import List


class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        res = []
        for S in range(1 << n):
            cur_res = []
            for i in range(n):
                if (S >> i) & 1:
                    cur_res.append(nums[i])
            res.append(cur_res)
        uni = {}
        r_res = []
        for item in res:
            item.sort()
            key = str(item)
            if key not in uni.keys():
                uni[key] = 1
                r_res.append(item)
        return r_res

---

最后更新: October 11, 2023