Partition array to K subsets

Partition array to K subsets

Partition array to K subsets

Given an integer array A[] of N elements, the task is to complete the function which returns true if the array A[] could be divided into K non-empty subsets such that the sum of elements in every subset is same.


Note: All elements of this array should be part of exactly one partition.

The output for each test case will be 1 if the array could be divided into k subsets else 0 .



Input:
2
5
2 1 4 5 6
3
5
2 1 5 5 6
3
Output:
1
0

Explanation:
Input : A[] = [2, 1, 4, 5, 6], K = 3
Output : 1, as we can divide above array into 3 parts with equal sum as (2, 4), (1, 5), (6)
Input : A[] = [2, 1, 5, 5, 6], K = 3
Output : 0, as it is not possible to divide above array into 3 parts with equal sum.

// bool partition(int start, int a[], vector<bool>  &visited,int K,int currentS,int targetS)
// {
//     if(K==1)
//     return true;
//     if(currentS==targetS)
//     {
//         return partition(0,a,visited,K-1,0,targetS);
//     }

//         for(int j=start;j<visited.size();++j)
//         {
//             if(!visited[j]&&currentS+a[j]<=targetS)
//             {
//                 visited[j]=true;
//                 if(partition(j+1,a,visited,K,currentS+a[j],targetS))
//                  return true;
//             }
//             visited[j]=false;
//         }
   
//     return false;
// }


bool partition(int a[],vector<int> v,int end,int sum)
{
//index is less than 0 then all element are discovered
    if(end<0)return true;
    // value of a[end] is assign to x to check possible to add in bucket
    int x=a[end];
    --end;
    for(int i=0;i<v.size();++i)
    {
// if current bucket is able add then call recursive function
// else try with another bucket
// recursion function if return false then back to substruct x from current bucket
        if(v[i]+x<=sum){
        v[i]+=x;
        if(partition(a,v,end,sum))
        return true;
        v[i]-=x;
        }
//after all ieraton of i to k any bucket remain vacant then break and return false
        if(v[i]==0)
        break;
       
    }
    return false;
   
}

bool isKPartitionPossible(int A[], int N, int K)
{
    int sumOfT=0;
    for(int i=0;i<N;++i)
    sumOfT+=A[i];
// if total sum is not divisible by K that cannot distribute sum into k bucket
    if(sumOfT%K!=0)
    return false;
   
   int s=sumOfT/K,i=N-1;
 
// to sort element to check last element is greater than (totalsum/k)
    sort(A,A+N);
    if(A[i]>s)
    return false;
// last element is exact equal to (totalsum/k) then decrease both k and i
    while(A[i]==s)
    {
        --i;
        --K;
    }

    vector<int> v(K,0);
    return partition(A,v,i,s);
    
}