Subsets II

Problem

https://leetcode.com/problems/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

Pattern

Array, Backtracking, Bit Manipulation

Approaches

Backtracking

Code

def subsetsWithDup(nums: list[int]) -> list[list[int]]:
    """Returns all possible sub-multisets of ``nums`` (including duplicates)."""
    nums = sorted(nums)
    result = []

    def backtrack(subset, i):
        result.append(subset.copy())

        for j in range(i, len(nums)):
            if j > i and nums[j] == nums[j - 1]:
                continue

            backtrack(subset + [nums[j]], j + 1)

    backtrack([], 0)
    return result

Test

>>> from subsets_ii__backtracking import subsetsWithDup
>>> sorted([sorted(s) for s in subsetsWithDup([1, 2, 2])])
[[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]
>>> sorted([sorted(s) for s in subsetsWithDup([0])])
[[], [0]]

subsets_ii__backtracking.subsetsWithDup(nums: list[int]) → list[list[int]]

Returns all possible sub-multisets of nums (including duplicates).