Partition to K Equal Sum Subsets

You are given an array of integers and an integer k. Your task is to determine whether the array can be partitioned into k non-overlapping subsets such that the sum of the elements in each subset is equal.

Let \( S = \sum_{i=1}^{n} nums[i] \). For a valid partition, \( S \) must be divisible by \( k \) and each subset must have a sum equal to \( T = \frac{S}{k} \).

You are required to use a backtracking approach to assign elements to each subset in order to achieve the target sum.

Example:

Input:
7 4
4 3 2 3 5 2 1
Output:
True

</p>

inputFormat

The input is given via stdin and consists of two lines:

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

outputFormat

Output a single line to stdout with either True or False depending on whether a valid partition exists.

## sample

7 4
4 3 2 3 5 2 1

True