有几个符号要回忆一下
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]