algo-aha

数组分成k个和相等的子集

• https://leetcode.com/problems/partition-to-k-equal-sum-subsets
• https://leetcode.com/problems/matchsticks-to-square

bool canPartitionKSubsets(vector<int>& nums, int k) {
    if (nums.size() < k) return false;
    int sum = 0;
    for (int num : nums) 
        sum += num;
    if (sum % k != 0) return false;
    
    vector<bool> visited(nums.size(), false);
    return search(nums, 0, visited, k, 0, sum / k);
}

// 从nums[idx..]取数，还要分割k个子集，当前子集已累积和subSum
bool search(vector<int> &nums, int idx, vector<bool> &visited, int k, int subSum, int target) {
    if (k == 0) return true;
    if (subSum == target) return search(nums, 0, visited, k - 1, 0, target);
    
    for (int i = idx; i < nums.size(); i++) {
        if (visited[i] || subSum + nums[i] > target) continue;

        visited[i] = true;
        if (search(nums, i + 1, visited, k, subSum + nums[i], target)) return true;
        visited[i] = false;
    }
    return false;
}