[LeetCode] Challenge log 90

Posted on |
90. Subsets II

Analysis: Simialr to 70. The key is to count the repetion times of number.

Alg1: DFS.

Alg2: Build as recur.

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

1
2
3
4
5
6
7
8
9
10
Input: [1,2,2]
Output:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]
Soulution:
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
# Alg1
class Solution:
    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        n = len(nums)
        if n == 0: return []

            
        # count dups
        count = {}
        for num in nums:
            if num not in count:
                count[num] = 1
            else:
                count[num] += 1
                 
        def dfs(count, st):
            if len(count) == 0:
                res.append(st)
                return
            key, val = count.popitem()
            for i in range(val+1):
                dfs(count, st + [key] * i)
            count[key] = val
        
        res = []
        dfs(count, [])
        return res
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
# Alg2
class Solution:
    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        n = len(nums)
        if n == 0:
            return []
        elif n == 1:
            return [nums, []]
        else:
            
            # count dups
            count = {}
            for num in nums:
                if num not in count:
                    count[num] = 1
                else:
                    count[num] += 1
                 
            # loops over dict    
            res = [[]]
            while len(count) > 0:
                key, val = count.popitem()
                temp = []
                for i in range(0, val+1):
                    temp += [x + [key] * i for x in res]       
                res = temp
            return res
0%