Backtracking: Partition to K Equal Sum Subsets

Problem Statement:

You are given an integer array and an integer K, you need to return true if you are able to divide the

Example

Input: [4,3,2,3,5,2,1], k = 4
Output: true
It is possible to divide into 4 sub array with equal sum as: (5), (1, 4), (2,3), (2,3)

Solution

In the recursive function we add the array element into a subset.

Then if the subset reaches the required sum, then we go for the next part recursively.

Else we backtrack for different set of elements.

Then while ding so, if the subsets reaches the required sum and is (k-1), then we return true.

Solution in C++

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<vector>
#include<set>

using namespace std;

bool backtrack(vector<int>& nums,vector<int>visited,int idx,int k,int currsum,int targetsum)
{
   // it means all the sub-sets has been found, hence return true
  if(k==1) 
      return true; 

   // it means, you found one subset, hence start to find another subset.
  if(currsum == targetsum) 
      return backtrack(nums,visited,0,k-1,0,targetsum);  

  for(int i=idx ; i<nums.size() ; i++)
  {
      // if the index is not visited, then it can be part of the current subset
      if(!visited[i])                                                
      {
          visited[i]=true;      
          if(backtrack(nums,visited,i+1,k,currsum+nums[i],targetsum)) 
            return true;  

          visited[i]=false;//for backtracking
      }
  }
  return false;
}
bool is_k_partition_possible(vector<int>& nums, int k) 
{
  vector<int>visited(nums.size(),false);
  int sum=0;
  for(auto x:nums) 
      sum+=x;

  if(sum%k!=0) 
      return false;
  
  int targetsum=sum/k;

  return backtrack(nums,visited,0,k,0,targetsum);
  
}

int main()
{
   vector<int> arr = {4,3,2,3,5,2,1};
   int k = 4;

   if(is_k_partition_possible(arr, k))
   {
      cout<<"Yes it is possible"<<endl;
   } 
   else
   {
      cout<<"No, it is not possible"<<endl;
   }



    return 0;
}

Output:

Yes it is possible