### 题目

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.

### 先排序，然后DFS回溯遍历所有组合

sum = 20, k = 4

sum of each subset = 20 / 4 = 5


排序后：
[1, 2, 2, 3, 3, 4, 5]


#### 代码

class Solution {
public boolean canPartitionKSubsets(int[] nums, int k) {
int sum = 0;
for (int n : nums) sum += n;
if (sum % k != 0) return false;
int targetSum = sum / k;
localNums = nums;
taken = new boolean[nums.length];
Arrays.sort(localNums);
int idx = nums.length - 1;
while (true) {
while (idx >= 0 && taken[idx]) idx--;
if (idx < 0) break;
if (!backtracking(targetSum, idx)) return false;
}
return true;
}

private int[] localNums;
private boolean[] taken;

private boolean backtracking(int sum, int idx) {
if (sum == 0) return true;
if (idx < 0 || sum < 0 || taken[idx]) return false;
int remain = sum - localNums[idx];
taken[idx] = true;
if (remain == 0 && idx == 0) return true;
for (int i = idx - 1; i >= 0; i--) {
if (backtracking(remain, i)) return true;
}
taken[idx] = false;
return false;
}
}