/// problem: https://leetcode.com/problems/partition-to-k-equal-sum-subsets/

class Solution {
public:

    int dpp[2+(1<<16)] , sum[2+(1<<16)];

    void init(vector<int>& nums){
        int tot = nums.size();
        for(int mask = 0 ; mask < (1<<tot) ; mask++){
            for(int i = 0 ; i < tot ; i++){
                if(mask & (1<<i)) sum[mask] += nums[i];
            }
        }
    }

    bool solve(vector<int>& nums , int mask, int cons)
    {
        if(dpp[mask] != -1) return dpp[mask];
        if(mask == 0) return 1;
        bool ans = 0;
        for(int sub = mask ; sub > 0 ; sub = (sub-1)&mask){
            if(sum[sub] == cons){
                ans |= solve(nums , mask ^ sub , cons);
            }
        }
        return dpp[mask] = ans;
    }

    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int sum = 0;
        for(int a:nums) sum += a;
        sum /= k;
        init(nums);
        memset(dpp,-1,sizeof dpp);
        int tot = nums.size();
        return solve(nums,(1<<tot) - 1,sum);
    }
};