有几个符号要回忆一下
s>>i 右移i位
s<<i 左移i位
s^(1<<i) ^表示异或
1&i 表示位与
s>>i & 1 这里先 >> 然后再 &
s>>i+1 这里先 i+1 然后再>>
第一种解法
nums 要分成k个列表 每个列表之和相等 必然是 target=sum(nums)//k
如果无法均分 那么就不成立
如果最大数字大于target 必然无法均分 不成立
需要划分得到k 个 和位target的组合 用求余比较合适
首先得到s 标记所有数字都可以用
如果s上所有数字都用完了 一定是true
遍历nums所有数字 从小到大依次选择 如果一个数字加上来超过target 再往下加肯定还是大于 则为false
如果一个数字从没有被使用过 (s>>i&1)==1 并且这个数字是最后一个没有被使用的数字(这里需要迭代 探索其他的组合会 只要加上这个数字就会符合条件的) 则返回true
如果以上条件都不满足 则为false
时间复杂度：
s一共有 2^n 种组合 每个s进到dp里都有一个长度为n的for循环 所以时间复杂度=n*2^n
空间复杂度：
主要是状态数组空间的开销 每有一种s 都要进一次dp算 需要2^n
from collections import defaultdict
class Solution(object):
def canPartitionKSubsets(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: bool
"""
# 用回归来做
target=sum(nums)//k
if target*k<sum(nums):
return False
nums.sort()
if nums[-1]>target:
return False
n=len(nums)
# s 再怎么大也不可能大于1<<n
dic={}
# @cache
def dp(s,per):
if s==0:
dic[(s,per)]=True
return True
for i in range(n):
if nums[i]+per>target:
break
# (s>>i)&1 ==1 表示 第i个数字没有被使用
# a=dp(s^(1<<i),(nums[i]+per)%target) # 这个把i改为0 加上第i个数字 继续做
aa=s^(1<<i)
bb=(nums[i]+per)%target
if (aa,bb) in dic:
if (s>>i)&1 and dic[(aa,bb)]:
dic[(s,per)]=True
return True
else:
if (s>>i)&1 and dp(aa,bb):
dic[(s,per)]=True
return True
dic[(s,per)]=False
return False
# (1<<n)-1 = 111111... 得到n个1 表示可用
return dp((1<<n)-1,0)
第二种解法
思路是把所有的情况都列举出来 s有2^n种
那么dp就有2^n种代表每一种是否探索过
cur_sum代表探索过后的当前和
第一种是所有数字都不使用
在这种情况下 遍历n 代表仅使用一个数字的情况 全都探索了得到当前和
下一种情况就在基于上轮的新增可探索范围内(后续的dp) 继续探索
把所有的情况都算出来之后
挑选所有数字都使用了的那种情况返回
时间复杂度
这个很明显 看循环就知道 n* 2^n
空间复杂度
dp,cur_sum 都要存储 2*2^n 就是 O(2^n)
from collections import defaultdict
class Solution(object):
def canPartitionKSubsets(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: bool
"""
# 用回归来做
target=sum(nums)//k
if target*k<sum(nums):
return False
nums.sort()
if nums[-1]>target:
return False
n=len(nums)
dp=[False]*(1<<n)
cur_sum=[0]*(1<<n)
dp[0]=True
# 这一种思路是把 所有的情况全都遍历一遍
for i in range(0,1<<n):
# 这里为啥是 not dp[i]
if not dp[i]:
continue
# 如果dp 是 true代表这个地方探索过
# 这个地方探索过 那么cur_sum才是有意义的 没探索过 加上cur_sum 没有用
for j in range(n):
if cur_sum[i]+nums[j]>target:
break
if i>>j&1==0:
if not dp[i|(1<<j)]:
dp[i|(1<<j)]=True
cur_sum[i|(1<<j)]=(cur_sum[i]+nums[j])%target
return dp[(1<<n)-1]
