Given an array of integers nums and a positive integer k, find whether it’s possible to divide this array into k non-empty subsets whose sums are all equal.

Example 1:

Input: nums = [4, 3, 2, 3, 5, 2, 1], k = 4
Output: True
Explanation: It's possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.

Note:

• 1 <= k <= len(nums) <= 16.
• 0 < nums[i] < 10000.

一句话题意

给定一个只包含正整数的数组，求是否可以将该数组中的元素分成K组，使每组的元素之和相等。

解题思路

乍一看，感觉只能暴力搜索。

另外，先搜值较大的数再搜值较小的数，这样效率会高很多。因为这样不会重复添加很多次小数字。

注意记录那些用过了，以及搜索过的状态。