[LeetCode] Partition to K Equal Sum Subsets

Problem: 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:

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.

Input: nums = [1,2,3,4], k = 3
Output: false

Approach: First we will check if SUM(nums) mod k is 0 or not. If not then we can safely return false. 

Otherwise we have a target_sum which SUM(nums) / k. We just need to find k subsets of nums whose sum is k. This is a backtracking problem. You can understand the logic by just looking at the code.

Implementation in C#:

    public bool CanPartitionKSubsets(int[] nums, int k) 

    {

        int sum = 0;

        for (int i = 0; i < nums.Length; ++i)

        {

            sum += nums[i];

        }

        // Impossible case

        if (sum % k != 0)

        {

            return false;

        }

        int targetSum = sum / k;

        bool[] visited = new bool[nums.Length];

        return KPartitionsPossible(nums, k, targetSum, 0, 0, visited);

    }

    

    private bool KPartitionsPossible(

        int[] nums,

        int k, 

        int targetSum, 

        int currSum,

        int index,

        bool[] visited)

    {

        // All the subsets found, return true.

        if (k == 0)

        {

            return true;

        }

        // Get 1 more subset, now find k - 1 subsets

        if (currSum == targetSum)

        {

            return KPartitionsPossible(nums, k - 1, targetSum, 0, 0, visited);

        }

        for (int i = index; i < nums.Length; ++i)

        {

            if (!visited[i] && currSum + nums[i] <= targetSum)

            {

                visited[i] = true;

                // If true then done return true.

                if (KPartitionsPossible(nums, k, targetSum, currSum + nums[i], i + 1, visited))

                {

                    return true;       

                }

                visited[i] = false;

            }

        }        

        return false;

    }

Complexity: O(k * 2 ^ n)