698. Partition to K Equal Sum Subsets

-

https://leetcode.com/problems/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.

 

Note:

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


---
Intuition

If the sum of all elements in array % k != 0
    return false

DFS on all combinations, and keep track of sums
    Terminate on last index .. reached here only if all sums are valid
         return true

    for (i = 0... k)
        if (sums[i] + nums[index] <= target)
            sums[i] += nums[index]
            if (dfs(nums, sums, index + 1, target))
                return true
            sums[i] -= nums[index]

    return false

This tries all combinations
Can optimize
Sort the array descending first

It exits early if any sum > target
---
Time - O(K ^ N)
Space - O(N)
---
Related problems
---