原题：
DiscussPick One
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，判断是否能把数组分成k个子数组，每个子数组元素和都相等。
思考过程：
一开始联想到了twoSum，后来发现子数组元素个数是不确定的，就比较棘手。看了以前CombinationSum，想到了要递归，最关键的是先把数组排序，复杂的题一定先想到把数组排序。但是排序后不能从前往后遍历，因为几个小的数可以代替大的数，但是大的数不能代替几个小的数。从后往前遍历就可以了。
解题思路：
先求出数组总和，除以k就是每个子数组的和。设置一个变量count记录目前找到的满足条件的子数组个数。用int型变量target标识当前与子数组和差多少。然后遍历寻找数组里值为target的值，如果没有就继续往前递归。如果找到，count++，返回true，把递给所经过的数组元素值设置为0，停止递归。最后判断是否所有数组元素为0以及count == k。
结果代码：
int[] nums;
int len;
int countOfSubsets = 0;//记录满足条件的子数组个数
public boolean canPartitionKSubsets(int[] nums, int k) {
this.nums = nums;
this.len = nums.length;
if (len == 0) return false;
Arrays.sort(nums);//先排序，复杂的题都先排序
int total = 0;
for (int i = 0;i < len;i++)
total += nums[i];
if (total % k != 0) return false;
int target = total / k;//先求出子数组元素总和应该为多少
for (int i = len - 1;i >= 0;i--)//几个小的数能代替大的数，大的数不能代替几个小的数，故倒着遍历数组
if (nums[i] > target)return false;
else if (nums[i] == 0) continue;//已经被纳进子数组的元素
else recursive(target,i);
for (int i = 0;i < len;i++)
if (nums[i] != 0) return false;
return countOfSubsets == k;
}
public boolean recursive(int target,int begin){
for (int i = begin;i >= 0;i--){
if (nums[i] == 0) continue;//被修改过的，直接跳过
if (nums[i] == target){
countOfSubsets++;
nums[i] = 0;
return true;
}
if (recursive(target - nums[i],i - 1)) {
nums[i] = 0;
return true;
}
}
return false;
}版权声明：本文为m0_37821950原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。