1209. Partition to K Equal Sum Subsets

Given an array nums and an integer k, determine whether nums can be partitioned into exactly k non-empty subsets all having the same sum. Return true or false. The input is JSON {nums, k}.

Input: JSON {nums, k}.

Output: Boolean — true or false.

Examples

Input: {"nums":[4,3,2,3,5,2,1],"k":4}
Output: true
Explanation: Four subsets each summing to 5.

Input: {"nums":[1,2,3,4],"k":3}
Output: false
Explanation: Total is not divisible by 3.

Input: {"nums":[1],"k":1}
Output: true
Explanation: One subset.

Constraints

• 1<=n<=16
• 1<=k<=n

Asked by