Given an integer array nums of unique elements, return all possible subsets (the power set).
The solution set must not contain duplicate subsets. Return the solution in any order.
Example 1:
Input: nums = [1,2,3] Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
Example 2:
Input: nums = [0] Output: [[],[0]]
Constraints:
1 <= nums.length <= 10-10 <= nums[i] <= 10nums are unique.Source
def subsets(nums):
"""Recursive approach.
f([a,b,c,d]) = [a] + f([b,c,d]) + [a, X] with X in f([b,c,d])
"""
def helper(arr):
if len(arr) == 1:
return [arr]
for element in arr:
powerset = helper(arr[1:])
return [[element], *powerset, *[[element] + s for s in powerset]] # unpack with *
result = [[]]
result.extend(helper(nums))
return result
def subsets(nums):
"""Alternative version of above solution."""
def helper(nums, path):
nonlocal result
result.append(path)
for i, _ in enumerate(nums):
helper(nums[i+1:], path + [nums[i]])
result = []
helper(nums, [])
return result
nums = [1,2,3]
subsets(nums)
[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
nums = [0]
subsets(nums)
[[], [0]]
Solve it both recursively and iteratively.
def subsets(nums):
"""Iterative approach"""
result = [[]]
for n in nums:
# Option A
# result += [[n] + subset for subset in result]
# Option B: using a generator
powerset = ([n] + subset for subset in result)
result.extend(list(powerset))
return result
Solve it using the built-in methodes reduce, combinations or using bit manipulations
from functools import reduce
def subsets(nums):
"""Using builtin reduce() method
"""
def helper(powerset, n):
new_set = []
for s in powerset:
new_set += s + [n],
return powerset + new_set
return reduce(helper, nums, [[]])
from functools import reduce
def subsets(nums):
"""One liner version of above solution"""
return reduce(lambda subsets, n: subsets + [s + [n] for s in subsets], nums, [[]])
from itertools import combinations
def subsets(nums):
"""Using builtin combinations() method which returns (tuples) subsequences of length r
combinations('ABCD', 2) --> AB AC AD BC BD CD
combinations('ABCD', 3) --> ABC ABD ACD BCD
"""
result = []
n = len(nums)
for i in range(n+1):
# Option A
result += map(list, combinations(nums, i))
# Option B
# result.extend(map(list, combinations(nums, i))) # use extend not append
return result
from itertools import combinations
def subsets(nums):
"""One liner version of above solution"""
n = len(nums)
return [s for i in range(n+1) for s in combinations(nums, i)]
def subsets(nums):
"""Using bit manipulation
[a, b, c, d]
x 0 0 0 0 = []
x 0 0 0 1 = [d]
x 0 0 1 0 = [c]
...
x 1 1 1 1 = [a, b, c, d]
"""
n = len(nums)
nb_bit = '{:0' + str(n) + 'b}' # '{0Xb:}' with X = len(nums)
result = []
for i in range(2**n):
bit_mask = nb_bit.format(i) # generate strings from 00...0 to 11...1
result += [nums[idx] for idx in range(n) if bit_mask[idx] == '1'],
return result
def subsets(nums):
"""One liner version of above solution"""
n = len(nums)
nb_bit = '{:0' + str(n) + 'b}'
bit_masks = (nb_bit.format(i) for i in range(2**n))
return [[nums[i] for i, on in enumerate(mask) if on == '1'] for mask in bit_masks]
from itertools import product
def subsets(nums):
"""Alternative solution using bit manipulation"""
n = len(nums)
bit_masks = product((0, 1), repeat=n) # generate (0,0..,0) (0,0..,1) ... (1,0..,0) ... (1,1..,1)
result = []
for mask in bit_masks:
result += [nums[i] for i, on in enumerate(mask) if on],
return result
from itertools import product
def subsets(nums):
"""One liner version of above solution"""
bit_masks = product((0, 1), repeat=len(nums))
return [[nums[i] for i, on in enumerate(mask) if on] for mask in bit_masks]