Problem
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],
[]
]
Notes
Three strategies to solve a subset problem:
Recursion, Backtracking, Bitmask
Recursion
Iterative version:
Start from empty array [[]].
Step 1: Take 1 into consideration, and add 1 to existing array [[], [1]]
Step 2: Take 2 into consideration, and add 2 to existing array [[], [1], [2], [1, 2]]
Step 3: Take 3 into consideration, and add 3 to existing array [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
DFS version:
[[]]
[[], [1]],
[[], [1], [1, 2]]
[[], [1], [1, 2], [1, 2, 3]]
[[], [1], [1, 2], [1, 2, 3], [1, 3]]
[[], [1], [1, 2], [1, 2, 3], [1, 3], [2]]
[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3]]
[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
Backtrack
Backtrack needs to know how many steps it shoud take to end.
[1, 2, 3]
Step 1: subsets of length 0: [[]]
Step 2: subsets of length 1: [[1], [2], [3]]
Step 3: subsets of length 2: [[1, 2], [2, 3], [1, 3]]
Step 4: subsets of length 3: [[1, 2, 3]]
Bitmask
The idea is that we map each subset to a bitmask of length n, where 1 on the ith position in bitmask means the presence of nums[i] in the subset, and 0 means its absence.
[1, 2, 3]
[0, 0, 0] -> []
[0, 0, 1] -> [3]
[0, 1, 0] -> [2]
[1, 0, 0] -> [1]
[1, 0, 1] -> [1, 3]
[0, 1, 1] -> [2, 3]
[1, 1, 0] -> [1, 2]
[1, 1, 1] -> [1, 2, 3]
Solution
Solution 1: dfs (recursion)
class Solution(object):
def subsets(self, nums):
res = []
self.dfs(sorted(nums), 0, [], res)
return res
def dfs(self, nums, index, path, res):
res.append(path)
for i in range(index, len(nums)):
self.dfs(nums, i + 1, path + [nums[i]], res)
print(Solution().subsets([1, 2, 3]))
Solution 2: iterative
class Solution:
def subsets(self, nums):
res = [[]]
for i in sorted(nums):
res += [item+[i] for item in res]
return res
print(Solution().subsets([1, 2, 3]))
Solution 3: backtrack
class Solution(object):
def subsets(self, nums):
output = []
for k in range(0, len(nums)+1):
temp = []
self.backtrack(0, k, nums, temp, output)
return output
def backtrack(self, begin, length, nums, temp, output):
if length == len(temp):
output.append(temp[:])
for i in range(begin, len(nums)):
temp.append(nums[i])
self.backtrack(i+1, length, nums, temp, output)
temp.pop()
print(Solution().subsets([1, 2, 3]))
Solution 4: bitmask
class Solution():
def subsets(self, nums):
n = len(nums)
output = []
for i in range(2**n, 2**(n+1)):
bitmask = bin(i)[3:]
output.append([nums[i] for i in range(n) if bitmask[i] == '1' ])
return output