Partition to K equal sum subsets | Leetcode solution | Dynamic programming.

Problem Tags: Medium, Dynamic Programming, Recursion

698. Problem Description:

Given an array of integers nums and a positive integer k, find whether it's 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's possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.

Note:

• 1 <= k <= len(nums) <= 16.
• 0 < nums[i] < 10000.

Problem Solution in C++ Programming Language:

code:

class Solution {

public:

    int total;

    bool solve(vector<int> &A,int sum,int idx,int k)

    {

        if(k==0) return true;

        

        if(sum==0) return solve(A,total,0,k-1);

            

        if(idx==A.size()) return false;

        

        for(int i=idx;i<A.size();i++)

        {

            if(A[i]<=sum && A[i]!=INT_MAX)

            {

                int temp=A[i];

                A[i]=INT_MAX;

                if(solve(A,sum-temp,i+1,k)) return true;

                A[i]=temp;

            }

        }

        return false;

    }

    

    bool canPartitionKSubsets(vector<int>& nums, int k) 

    {

        int sum=0;

        for(auto x:nums)

            sum+=x;

        

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

        total=sum/k;

        return solve(nums,sum/k,0,k);

    }

};

Please share your reviews.

Thanks for reading 😊👍