Leetcode•Aug 11, 2025

Partition to K Equal Sum Subsets

Hazrat Ali

Leetcode

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

Solution

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {boolean}
 */
const canPartitionKSubsets = (nums, k) => {
 
  const sum = nums.reduce((total, num) => total + num);
  if (sum % k !== 0 || nums.some(num => num > sum / k)) {
    return false;
  }

 
  const used = new Set();

 
  return (function search(start, target) {
   
    if (used.size === nums.length) {
      return true;
    }

   
    if (target < 0) {
      return false;
    }

   
    if (target === 0) {
      return search(0, sum / k);
    }

    for (let i = start; i < nums.length; i++) {
      if (!used.has(i)) {
        used.add(i);
        if (search(i + 1, target - nums[i])) {
          return true;
        }
        used.delete(i);
      }
    }

    return false;
  })(0, sum / k);
};





Comments