90. 子集 II(Medium)

题目描述

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

样例

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

题目解析

本题 和 子集(78) 一样，就是允许了重复元素。加入去重操作，也是一道模板题。

Python 代码示例

def backtracking(nums, visited, ans, cur, tmp):
    ans.append(tmp[:])
    for i in range(cur, len(nums)):
        if i > 0 and nums[i - 1] == nums[i] and not visited[i - 1]:
            continue
        tmp.append(nums[i])
        visited[i] = 1
        backtracking(nums, visited, ans, i + 1, tmp)
        tmp.pop()
        visited[i] = 0
    
    
class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        visited = [0] * len(nums)
        ans = []
        backtracking(nums, visited, ans, 0, [])
        return ans 

参考资料

回溯算法：求子集问题！