698. Partition to K Equal Sum Subsets

Given an array of integers nums and a positive integer k, find whether it's possible to divide this array into k non-empty subsets whose sums are all equal.

Example 1:

Input: nums = [4, 3, 2, 3, 5, 2, 1], k = 4
Output: True
Explanation: It's possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.

Note:

• 1 <= k <= len(nums) <= 16.

• 0 < nums[i] < 10000.

之前416. Partition Equal Subset Sum可以只找數列中是否有數列子集合能形成總和的一半，因為只要找到一個子集合能加總成總和一半，剩下的子集合必然能形成另一個和為數列總和一半的組合。但這題要求k個子集合，那最直接的方法就是recursive backtracking去找看看所有可能的情形。

// Backtracking
bool helper(vector<int>& nums, vector<bool>& visited, int k, int target, int curSum, int start) {
    if (k == 1) return true;
    if (curSum > target) return false;
    if (curSum == target) return helper(nums, visited, k - 1, target, 0, 0); // finish a subset and start a new one
    for (int i = start; i < nums.size(); ++i) {
        if (visited[i]) continue;
        visited[i] = true;
        if (helper(nums, visited, k, target, curSum + nums[i], i + 1)) return true;
        visited[i] = false;
    }
    return false;
}
bool canPartitionKSubsets(vector<int>& nums, int k) { // time: O(k * n^2); space: O(n)
    int sum = accumulate(nums.begin(), nums.end(), 0);
    if (k <= 0 || sum % k != 0) return false;
    vector<bool> visited(nums.size(), false);
    return helper(nums, visited, k, sum / k, 0, 0);
}

416. Partition Equal Subset Sum