1
class Solution {
2
 public:
3
  unordered_map<string, int> dp;
4
  int solve(vector<int> &nums, int target, int remain, int i, int vis, int k) {
5
    if (k == 1) return 1;
6

7
    // memorization addition
8
    string t = to_string(i) + "_" + to_string(remain) + "_" + to_string(k) + "_" + to_string(vis);
9
    if (dp.find(t) != dp.end()) return dp[t];
10

11
    if (remain == 0) {
12
      return dp[t] = solve(nums, target, target, nums.size() - 1, vis, k - 1);
13
    }
14
    for (int j = i; j >= 0; --j) {
15
      if (((vis >> j) & 1) || remain - nums[j] < 0) continue;
16
      vis = vis | (1 << j);
17
      if (solve(nums, target, remain - nums[j], j - 1, vis, k)) return dp[t] = 1;
18
      vis = vis & ~(1 << j);
19
    }
20
    return dp[t] = 0;
21
  }
22
  bool canPartitionKSubsets(vector<int> &nums, int k) {
23
    int sum = accumulate(nums.begin(), nums.end(), 0);
24
    if (sum % k != 0) return false;
25
    int vis = 0;
26
    return solve(nums, sum / k, sum / k, nums.size() - 1, vis, k);
27
  }
28
};