Equal Sum Partitioning

Given an array of positive integers, determine if it is possible to partition the array into exactly k non-empty subsets such that the sum of the elements in each subset is equal.

The problem is only feasible if the total sum of the array is divisible by k. Use backtracking to explore different possible partitions.

For example, the array [4, 3, 2, 3, 5, 2, 1] can be partitioned into 4 subsets with equal sum (each subset summing to 5) since 4 + 3 + 2 + 3 + 5 + 2 + 1 = 20 and 20 / 4 = 5.

inputFormat

The first line contains two integers n and k, where n is the number of elements in the array, and k is the number of subsets to partition the array into.

The second line contains n space-separated integers denoting the elements of the array.

outputFormat

Output a single line: "True" if the array can be partitioned into k subsets with equal sum, or "False" otherwise.

7 4
4 3 2 3 5 2 1

True