Subsets II
franklinqin0 ArrayBacktrackingBit
# Solution
This problem follows the easier one.
# Binary Sorted Subsets
Say there are only five 's in nums, then the following all produce [2 2]:
2 2 2 2 2
---------
1 1 0 0 0 -> [2 2]
1 0 0 0 1 -> [2 2]
0 1 0 1 0 -> [2 2]
0 0 0 1 1 -> [2 2]
...
1
2
3
4
5
6
7
2
3
4
5
6
7
How do we only take ? By observation, there are 3 cases:
- start w/ 's then followed by 's:
1 1 0... - start w/ but have 's inbetween:
1 0... 1 - start w/ :
0... 1...or0... 1... 0...
To only take the 1st case and eliminate the rest 2 cases' duplicates, see the highlighted area below.
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
nums.sort()
n = len(nums)
res = []
for mask in range(1 << n):
temp = []
illegal = False
for i in range(n):
not_dup = (i == 0) or (i > 0 and nums[i-1] == nums[i])
if mask & (1 << i):
# num[i] is duplicate && the former digit of mask is 0
if i>0 and nums[i-1]==nums[i] and mask&(1<<(i-1))==0:
illegal = True
break
else:
temp.append(nums[i])
if not illegal:
res.append(temp)
return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21