/
78.subsets.py
112 lines (99 loc) · 2.64 KB
/
78.subsets.py
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#
# [78] Subsets
#
# https://leetcode.com/problems/subsets/description/
#
# algorithms
# Medium (47.99%)
# Total Accepted: 282.2K
# Total Submissions: 587.3K
# Testcase Example: '[1,2,3]'
#
# Given a set of distinct integers, nums, return all possible subsets (the
# power set).
#
# Note: The solution set must not contain duplicate subsets.
#
# Example:
#
#
# Input: nums = [1,2,3]
# Output:
# [
# [3],
# [1],
# [2],
# [1,2,3],
# [1,3],
# [2,3],
# [1,2],
# []
# ]
#
#
# backtracing
# O(N * 2^N); O(2^N) solusions multiply each need O(N) to construct a array result
# 20 ms, faster than 71.68%
class Solution(object):
def subsets(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
results = []
tmp = []
self.helper(sorted(nums), tmp, 0, results)
return results
def helper(self, nums, tmp, start, results):
results.append(tmp[:]) # another copy results.append(list(tmp))
for i in range(start, len(nums)):
tmp.append(nums[i])
self.helper(nums, tmp, i + 1, results)
tmp.pop()
# bit manipulation
# O(N * 2^N)
# suppose [1, 2, 3] initially the 8 subsets are all empty
# a way to visualize this idea. That is,
# 1 appears once in every two consecutive subsets,
# 2 appears twice in every four consecutive subsets,
# 3 appears four times in every eight subsets, shown in the following:
# [], [], [], [], [], [], [], []
# [], [1], [], [1], [], [1], [], [1]
# [], [1], [2], [1, 2], [], [1], [2], [1, 2]
# [], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]
class Solution2(object):
def subsets(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
size = len(nums)
num_subset = 2 ** size
results = [[] for _ in range(num_subset)]
for i in range(size):
for j in range(num_subset):
if ((j >> i) & 1):
results[j].append(nums[i])
return results
# iterative
# 2^0 + 2^1 + ... + 2^N = O(2^N) * O(N)
# suppose [1, 2, 3] initially and the results = [[]]
# copy every item and append nums[i] to new copy one
# for 1 [[], [1]]
# for 2 [[], [1], [2], [1, 2]]
# for 3 [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
#
# 24 ms, faster than 39.46%
class Solution3(object):
def subsets(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
results = [[]]
size = len(nums)
for i in range(size):
for j in range(len(results)):
tmp = results[j] + [nums[i]]
results.append(tmp)
return results