划分为k个相等的子集

698. 划分为k个相等的子集
nums = [4, 3, 2, 3, 5, 2, 1], k = 4
将nums分为4个子集，每个子集的和相同。4个子集的和为4*某个数，就等于nums的和。因此，如果sum(nums)除以k有余数，则不能划分为k个子集，返回false。如果数组中最大的那个数大于sum(nums)/k（平均数），则这个数怎么也不能成为一个子集，因此也不能划分，返回false。
思路是因为数组长度16，可以用一个整数s的二进制表示。数组中哪个数已经被用了，哪个位就是0，否则为1。一开始为(1< ^表示异或，即1和1得到0，这样就把不占用变成占用了。
记录下每个s状态是否可行，就可以用记忆化搜索。
c++也有lamdba表达式。
[capture list ] ( parameter list) -> return type { function body }
function dfs = [&](int s, int p)->bool{}

   capture list :  捕获列表， 一个lambda 所在函数中定义的局部变量的列表，通常为空
   return  type :  返回类型
   parameter list：参数列表
   function body: 函数体 

class Solution {
public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int all = accumulate(nums.begin(), nums.end(), 0);
        if (all % k > 0) {
            return false;
        }
        int per = all / k; 
        sort(nums.begin(), nums.end());
        if (nums.back() > per) {
            return false;
        }
        int n = nums.size();
        vector<bool> dp(1 << n, true);
        function<bool(int,int)> dfs = [&](int s, int p)->bool {
            if (s == 0) {
                return true;
            }
            if (!dp[s]) {
                return dp[s];
            }
            dp[s] = false;
            for (int i = 0; i < n; i++) {
                if (nums[i] + p > per) {
                    break;
                }
                if ((s >> i) & 1) {
                    if (dfs(s ^ (1 << i), (p + nums[i]) % per)) {
                        return true;
                    }
                }
            }
            return false;
        };
        return dfs((1 << n) - 1, 0);
    }
};

之所以可以用(p + nums[i]) % per)判断是否可以用数组组成k个总和为per的组，是因为上面已经判断了nums[i] + p > per，就限定p+现在的数只能小于等于per。