子集生成方法
回溯法
请参考回溯法blog
有重复的和无重复的两种，无重复的就是[1,2,2]里的是[1,2]的子集只有一个
时间复杂度O(2**n)
无重复的
python3:
# 回溯法，枚举选哪个 O(2**n)
# 不去重的
def subset_with_backtrack(self, nums: List):
n = len(nums)
res = []
def backtrack(start: int, tmp: List):
cp = tmp.copy()
nonlocal res
res.append(cp)
for i in range(start, n):
tmp.append(nums[i])
# 选了
backtrack(i + 1, tmp)
tmp.pop()
# 没选
backtrack(0, [])
return res
# 回溯法2, 选或不选 O(2**n)
# 不去重的
def subset_with_backtrack2(self, nums: List):
n = len(nums)
res = []
def backtrack(index: int, tmp: List):
if index == n:
nonlocal res
cp = tmp.copy()
res.append(cp)
return
# 不选
backtrack(index + 1, tmp)
# 选
tmp.append(nums[index])
backtrack(index + 1, tmp)
# 恢复现场
tmp.pop()
backtrack(0, [])
return res
过滤掉有重复的code
python3
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
def backtrack(nums, start, tempList: List[int], res):
res.append(tempList.copy())
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i-1]: # skip duplicates
continue
tempList.append(nums[i])
backtrack(nums, i + 1, tempList, res)
tempList.pop()
return
nums.sort()
res = []
backtrack(nums, 0, [], res)
print(res)
return res
二进制法
二进制法复杂度比回溯法多个n. 时间复杂度O(2**n * n)
nums = [1, 2, 3, 4, 5]
limit = 1 << 5
res = [[] for _ in range(limit)]
for i in range(1 << len(nums)):
for j in range(len(nums)):
if (1 << j) & i > 0:
res[i].append(nums[j])
print(res, len(res))
下面是一些集合的操作
空集 s=0
只含有第i个元素 1<<i
含有全部n个元素 （1<<n）-1
判断第i个元素是否属于集合S S>>i &1
向集合中加入第i个元素 s|=1<<i
从集合中去除元素i s&~(1<<i)
集合S和集合T的并集 S|T
集合S和集合T的交集 S&T
枚举法
这个一般是求和之类的使用，否则会涉及已有数据的拷贝。
下面每次加入一个元素，是求子集sum value
def getSum(nums):
res = {0}
for num in nums:
res |= {i+num for i in res}
return sorted(list(res))
例题
使用了枚举法，求每个子集和的集合
class Solution:
def minAbsDifference(self, nums: List[int], goal: int) -> int:
n = len(nums)
ans = float('inf')
def getSum(nums):
res = {0}
for num in nums:
res |= {i+num for i in res}
return sorted(list(res))
lsum = getSum(nums[:n//2])
rsum = getSum(nums[n//2:])
i, j = 0, len(rsum)-1
while i < len(lsum) and j >= 0:
tmp = lsum[i] + rsum[j]
ans = min(ans, abs(tmp - goal))
if tmp > goal:
j -= 1
elif tmp == goal:
return ans
else:
i += 1
return ans