三个月算法进阶--day23
目录
记录
leetcode第78题子集
递归
直观，逐渐增加规模
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
output = [[]]
for num in nums:
output += [curr + [num] for curr in output]
return output
回溯
全排列/组合/子集问题
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
def backtrack(first = 0, curr = []):
if len(curr) == k:
output.append(curr[:])
for i in range(first, n):
curr.append(nums[i])
backtrack(i + 1, curr)
curr.pop()
output = []
n = len(nums)
for k in range(n + 1):
backtrack()
return output
二进制
基于二进制位掩码和对应位掩码之间的映射字典，只需生成从0..00到1..11的所有n位掩码
纪念Donald E. Knuth
执行n的左位移位相当于乘以2**n，3 « 4 值为48
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
output = []
nth_bit = 1 << n
for i in range(2**n):
# 向左边填充0，或使用2**n到2**(n+1)
bitmask = bin(i | nth_bit)[3:]
output.append([nums[j] for j in range(n) if bitmask[j] == '1'])
return output
库函数
itertools.combinations(nums, k)