35. Partition to K Equal Sum Subsets

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.

Solution:

Approach:(Recursion and backtracking) We use a subset array and a visited array

class Solution
{
public:
    bool checkSubsetSum(vector<int> &nums, vector<int> &subsetSum, vector<bool> &visited, int targetSum, int idxArr, int k, int pos)
    {
        if (subsetSum[idxArr] == targetSum)
        {
            if (idxArr == k - 1)
            {
                return true;
            }

            return checkSubsetSum(nums, subsetSum, visited, targetSum, idxArr + 1, k, 0);
        }

        for (int i = pos; i < nums.size(); i++)
        {

            if (visited[i])
            {
                continue;
            }

            if ((subsetSum[idxArr] + nums[i]) <= targetSum)
            {
                subsetSum[idxArr] += nums[i];
                visited[i] = true;

                bool x = checkSubsetSum(nums, subsetSum, visited, targetSum, idxArr, k, i + 1);
                if (x)
                {
                    return true;
                }

                visited[i] = false;
                subsetSum[idxArr] -= nums[i];
            }
        }

        return false;
    }

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

        if (k == 1)
        {
            return true;
        }

        int s = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            s += nums[i];
        }

        if (s % k != 0)
        {
            return false;
        }

        int targetSum = s / k;
        vector<int> subsetSum(k, 0);
        vector<bool> visited(nums.size(), false);

        bool res = checkSubsetSum(nums, subsetSum, visited, targetSum, 0, k, 0);

        return res;
    }
};