Last updated on January 10th, 2025 at 05:07 am

Here, we see a Partition to K Equal Sum Subsets LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Array

Companies

Google

Level of Question

Medium

Partition to K Equal Sum Subsets LeetCode Solution

1. Problem Statement

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

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is “Backtracking”. Backtracking is a general algorithmic technique that involves exploring all possible solutions to a problem by building a solution incrementally and abandoning a solution as soon as it is determined that it cannot lead to a valid solution.

This problem specifically involves partitioning an array into k subsets with equal sums, which is a classic Subset Partitioning Problem. The backtracking approach is used to explore all possible ways to partition the array into subsets while ensuring the constraints are met.

3. Code Implementation in Different Languages

3.1 Partition to K Equal Sum Subsets C++

class Solution {
public:
	bool canPartitionKSubsets(vector<int>& nums, int k) {
		int sum = 0;
		sum = accumulate(nums.begin(), nums.end(), sum);
		if (nums.size() < k || sum % k) return false;
		vector<int>visited(nums.size(), false);
		return backtrack(nums, visited, sum / k, 0, 0, k);
	}
	bool backtrack(vector<int>& nums,vector<int>visited, int target, int curr_sum, int i, int k) {
		if (k == 1) return true;
		if (curr_sum == target) return backtrack(nums, visited, target, 0, 0, k-1);
		for (int j = i; j < nums.size(); j++) {
			if (visited[j] || curr_sum + nums[j] > target) continue;
			visited[j] = true;
			if (backtrack(nums, visited, target, curr_sum + nums[j], j+1, k)) return true;
			visited[j] = false;
		}
		return false;
	}
};

3.2 Partition to K Equal Sum Subsets Java

class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum=0;
        for(int i:nums){
            sum+=i;
        }
        if(sum%k!=0 || nums.length<k) return false;
        Arrays.sort(nums);
        return canPartitionKSubsets(nums,sum/k,nums.length-1,new int[k]);
    }
    public boolean canPartitionKSubsets(int a[],int target,int i,int bucket[]){
        if(i==-1)
            return true;
        for(int j=0;j<bucket.length;j++){
            if(bucket[j]+a[i]<=target){
                bucket[j]+=a[i];
                if(canPartitionKSubsets(a,target,i-1,bucket))
                    return true;
                bucket[j]-=a[i];
            }
            if(bucket[j]==0)
                break;
        }
        return false;
    }
}

3.3 Partition to K Equal Sum Subsets JavaScript

var canPartitionKSubsets = function(nums, k) {
  const total = nums.reduce((sum, num) => sum + num, 0);
  if (total % k !== 0) {
    return false;
  }
  const target = total / k;
  const visited = new Array(nums.length).fill(false);
  const canPartition = (start, numberOfSubsets, currentSum) => {
    if (numberOfSubsets === 1) {
      return true;
    }
    if (currentSum === target) {
      return canPartition(0, numberOfSubsets - 1, 0);
    }
    for (let i = start; i < nums.length; i++) {
      if (!visited[i]) {
        visited[i] = true;
        if (canPartition(i + 1, numberOfSubsets, currentSum + nums[i])) {
          return true;
        }
        visited[i] = false;
      }
    }
    return false;
  };
  return canPartition(0, k, 0);
};

3.4 Partition to K Equal Sum Subsets Python

class Solution(object):
    def canPartitionKSubsets(self, nums, k):
	    total = sum(nums)
	    if total % k:
		    return False
	    reqSum = total // k
	    subSets = [0] * k
	    nums.sort(reverse = True)
	    def recurse(i):
		    if i == len(nums):    
			    return True
		    for j in range(k):
			    if subSets[j] + nums[i] <= reqSum:
				    subSets[j] += nums[i]
				    if recurse(i + 1):
					    return True
				    subSets[j] -= nums[i]
				    if subSets[j] == 0:
					    break
		    return False
	    return recurse(0)

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(k * 2n)	O(n)
Java	O(k * 2n)	O(k + n)
JavaScript	O(k * 2n)	O(n)
Python	O(k * 2n)	O(k + n)