forked from keon/algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathsubsets_unique.py
More file actions
48 lines (37 loc) · 1.24 KB
/
subsets_unique.py
File metadata and controls
48 lines (37 loc) · 1.24 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
"""
Unique Subsets
Given a collection of integers that might contain duplicates, return all
possible unique subsets (the power set without duplicates).
Reference: https://leetcode.com/problems/subsets-ii/
Complexity:
Time: O(2^n) where n is the number of elements
Space: O(2^n) to store all subsets
"""
from __future__ import annotations
def subsets_unique(nums: list[int]) -> list[tuple[int, ...]]:
"""Return all unique subsets of a list that may have duplicates.
Args:
nums: A list of integers, possibly with duplicates.
Returns:
A list of unique tuples representing each subset.
Examples:
>>> sorted(subsets_unique([1, 2, 2]))
[(), (1,), (1, 2), (1, 2, 2), (2,), (2, 2)]
"""
found: set[tuple[int, ...]] = set()
_backtrack(found, nums, [], 0)
return list(found)
def _backtrack(
found: set[tuple[int, ...]],
nums: list[int],
stack: list[int],
position: int,
) -> None:
"""Recursive helper that includes or excludes each element."""
if position == len(nums):
found.add(tuple(stack))
else:
stack.append(nums[position])
_backtrack(found, nums, stack, position + 1)
stack.pop()
_backtrack(found, nums, stack, position + 1)