1. PartitionKSubsets.md

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

Input: nums = [4,3,2,3,5,2,1], k = 4 Output: true Explanation: It is possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.

Example 2:

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

My idea was to extend the idea of equal partition sum algorithm. In equal partition sum , we are trying to find if there is exists a subset , whose sum is equals to totalsum/2.

On similar line , in this problem we are trying to find a sum = totalsum/4.

But the thing is that we need to be sure that there exists K groups where each group with sum = totalsum/4. This approach will fail for test cases:

nums = [2,2,2,2,3,4,5] and k=4 where totalsum = 24, targetsum=6. There exists only 2 groups with target_sum = 6 , but actually we need 4 groups with target_sum=6.

Failure Approach passed: 100+ test cases

class Solution(object):
    def canPartitionKSubsets(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: bool
        """
        total_sum = sum(nums)
        if total_sum % k != 0:
            return False
        
        def canPartitionKSubsets(idx, target_sum):
            if target_sum == 0:
                return 1
            
            if idx >= len(nums) or target_sum < 0:
                return 0
            
            if dp[idx][target_sum] == -1:
                if nums[idx] <= target_sum:
                    if canPartitionKSubsets(idx+1, target_sum-nums[idx]) == 1:
                        dp[idx][target_sum] = 1
                        return 1
                dp[idx][target_sum] = canPartitionKSubsets(idx+1, target_sum)             
            return dp[idx][target_sum]

        target_sum = total_sum/k
        n = len(nums)
        dp = [[-1 for _ in range(target_sum+1)] for _ in range(n)]
        return True if canPartitionKSubsets(0, target_sum) == 1 else False

Success Approach

bool backtrack(vector < int > & arr, int i, int reqSum, int currSum, vector < bool > & isVisited, int k) {
  if (k == 0)
    return true;
  if (reqSum == currSum)
    return backtrack(arr, 0, reqSum, 0, isVisited, k - 1);

  if (i == arr.size())
    return false;

  if (!isVisited[i] && arr[i] + currSum <= reqSum) {
    isVisited[i] = true;
    if (backtrack(arr, i + 1, reqSum, currSum + arr[i], isVisited, k))
      return true;
    isVisited[i] = false;
  }

  return backtrack(arr, i + 1, reqSum, currSum, isVisited, k);
}

bool canPartitionIntoKSubsets(vector < int > & arr, int k) {

  int sum = 0;
  for (int ele: arr) sum += ele;
  if (sum % k != 0) return false;

  int n = arr.size();

  vector < bool > vis(n, false);
  return backtrack(arr, 0, sum / k, 0, vis, k);
}

Time complexity: O(k*2^n), for every subset we traverse the whole array and make two recursive calls almost in each traversal.