Partition Array into K Subsets with Equal Sum

You are given an array of integers and a positive integer \(k\). Your task is to determine if you can partition the array into \(k\) non-empty subsets such that the sum of the elements in each subset is exactly the same. In other words, if the sum of all elements is \(S\), then each subset must sum to \(\frac{S}{k}\), provided that \(S\) is divisible by \(k\).

This problem requires efficient backtracking to explore possible partitions of the array. Note that each subset must be non-empty and every element must belong to exactly one subset.

Constraints:

• The number of elements \(n\) may be up to a moderate size.
• \(k\) is a positive integer and \(1 \leq k \leq n\).

If the total sum \(S\) is not divisible by \(k\), the answer is immediately False. Otherwise, the target sum for each subset is \(\frac{S}{k}\). Use recursion and backtracking to try placing numbers into subsets and determine whether a valid partition exists.

inputFormat

The input is read from standard input (stdin) and has the following format:

n k
a1 a2 a3 ... an

Here, the first line contains two integers: \(n\), the number of elements in the array, and \(k\), the number of subsets. The second line contains \(n\) space-separated integers representing the elements of the array.

outputFormat

Output to standard output (stdout) a single line with True if it is possible to partition the array into \(k\) subsets with equal sum, or False otherwise.

## sample

7 4
4 3 2 3 5 2 1

True