Here, We see Partition to K Equal Sum Subsets LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Partition to K Equal Sum Subsets LeetCode Solution

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

Partition to K Equal Sum Subsets Leetcode Solution 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;
	}
};Code language: PHP (php)

Partition to K Equal Sum Subsets Leetcode Solution 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;
    }
}Code language: PHP (php)

Partition to K Equal Sum Subsets Leetcode Solution 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);
};Code language: JavaScript (javascript)

Partition to K Equal Sum Subsets Leetcode Solution 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)Code language: HTML, XML (xml)