Partition to K Equal Sum Subsets

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

Let \( total\_sum \) be the sum of all elements in the array. In order for a partition to exist, it is necessary that \( total\_sum \) is divisible by \( k \). The target sum for each subset will be \( \frac{total\_sum}{k} \). Your task is to decide whether such a partitioning exists.

Input: The first line contains two integers n and k. The second line contains n integers representing the array.

Output: Output a single line with either True if the partition exists, or False otherwise.

inputFormat

The input is given from stdin in the following format:

n k
a1 a2 a3 ... an

Where n is the number of elements, k is the desired number of equal sum subsets, and a1, a2, ..., an are the array elements separated by spaces.

outputFormat

The output is a single line to stdout that prints True if the array can be partitioned into k subsets with equal sum, and False otherwise.

7 4
4 3 2 3 5 2 1

True