## Algorithm

Problem Name: 698. Partition to K Equal Sum Subsets

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
```

Constraints:

• `1 <= k <= nums.length <= 16`
• `1 <= nums[i] <= 104`
• The frequency of each element is in the range `[1, 4]`.

## Code Examples

### #1 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const canPartitionKSubsets = function(nums, k) {
const sum = nums.reduce((ac, el) => ac + el, 0)
return k !== 0 && sum % k === 0 && canPartition(0, nums, [], k, 0, sum / k)

};

function canPartition(start, nums, seen, k, sum, target) {
if(k === 1) return true
if (sum === target) {
return canPartition(0, nums, seen, k - 1, 0, target)
}
for(let i = start; i < nums.length; i++) {
if (!seen[i]) {
seen[i] = true
if(canPartition(i + 1, nums, seen, k, sum + nums[i], target)> {
return true
}
seen[i] = false
}
}
return false
}
``````
Copy The Code &

Input

cmd
nums = [4,3,2,3,5,2,1], k = 4

Output

cmd
true

### #2 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def canPartitionKSubsets(self, nums, k):
def dfs(i, sums):
if i == n:
return True
for j in range(k):
if sums[j] + nums[i] <= target:
sums[j] += nums[i]
if dfs(i + 1, sums):
return True
sums[j] -= nums[i]
return False
nums.sort(reverse = True)
sm = sum(nums)
if sm % k: return False
target, n = sm // k, len(nums)
return dfs(0, [0] * k)
``````
Copy The Code &

Input

cmd
nums = [4,3,2,3,5,2,1], k = 4

Output

cmd
true

### #3 Code Example with C# Programming

```Code - C# Programming```

``````
using System;

namespace LeetCode
{
public class _0698_PartitionToKEqualSumSubsets
{
public bool CanPartitionKSubsets(int[] nums, int k)
{
int sum = 0, max = int.MinValue;
foreach (var num in nums)
{
sum += num;
max = Math.Max(max, num);
}

if (max > sum / k || sum % k != 0) return false;
return CanPartitionKSubsets(nums, k, new bool[nums.Length], sum / k, 0, 0);
}

private bool CanPartitionKSubsets(int[] nums, int k, bool[] visited, int target, int current, int index)
{
if (k == 1) return true;
if (target == current)
return CanPartitionKSubsets(nums, k - 1, visited, target, 0, 0);

for (int i = index; i  <  nums.Length; i++)
{
if (visited[i]) continue;
if (current + nums[i] > target) continue;

visited[i] = true;

if (CanPartitionKSubsets(nums, k, visited, target, current + nums[i], i + 1))
return true;

visited[i] = false;
}

return false;
}
}
}
``````
Copy The Code &

Input

cmd
nums = [1,2,3,4], k = 3

Output

cmd
false