Partition to K Equal Sum Subsets

Problem

Given an integer array nums and an integer k, return true if it is 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 is possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.

Example 2:

Input: nums = [1,2,3,4], k = 3
Output: false

 

Constraints:

• 1 <= k <= nums.length <= 16
• 1 <= nums[i] <= 104
• The frequency of each element is in the range [1, 4].

Solution

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {boolean}
 */
var canPartitionKSubsets = function(nums, k) {
    const sum = nums.reduce((acc, cur) => acc + cur, 0);
    if (sum % k !== 0) {
        return false;
    }
    const target = sum / k;
    const used = Array(nums.length).fill(false);
    return canPartition(nums, 0, used, k, target, 0);
};

var canPartition = function(nums, start, used, k, target, curSum) {
    if (k === 1) { // all subsets found
        return true;
    } else if (curSum > target) { // backtrack
        return false;
    } else if (curSum === target) { // one subset found, attempt to find next subset
        return canPartition(nums, 0, used, k - 1, target, 0);
    } else {
        for (let i = start; i < nums.length; i++) {
            if (used[i]) { // element already used
                continue;
            }
            used[i] = true;
            if (canPartition(nums, i + 1, used, k, target, curSum + nums[i])) {
                return true;
            }
            used[i] = false;
        }
    }
    return false;
};

We will implement a backtracking (DFS) solution. We attempt to find k - 1 subsets that each sum up to sum(nums) / k by testing all possible subsets of nums. Note that the kth subset can be formed by the left overs of nums after finding the first k - 1 subsets, so there's no need to explicitly find it ourselves.