698. 划分为k个相等的子集
【回溯法】用回溯法来思考这个问题的话其实思路是很简单的,还是以样例1为例:
4,3,2,3,5,2,1分成4组
首先计算sum/4 = 5,这样就可以创造出四个容量为5的桶bucket,我们可以创建一个int[]类型的数组bucket全部初始化为5来记录每个桶剩下的容量。下面开始从t=0,也就是第一个元素开始对数和桶进行回溯。
1.t = 0时,也就是所对于第一个元素4,他有四种选择,0-3号桶他都可以放,因此用i遍历这三个桶,当放进一个桶时,就把他的容量bucket[i] - nums[t],然后继续进t + 1层,同时不要忘记回到当前层时再把bucket[i] + 回去,然后i继续向后走,把第t个放进新的i桶中,继续t+1层以及回溯bucket。
2.t = 1时,已经进入到下一层,继续对第二个元素这样操作,同时这里可以稍微进行一点剪枝:当bucket[i] < nums[t]很明显已经不符合条件了,这里直接就可以不用继续向下了。
3.直到t = nums.length,也就是对每个元素都放好了桶时,就可以判断此时每个bucket是否都是0了,如果是0,就说明平分好了。
于是第一版的基础回溯就做出来
class Solution {
public boolean backTrack(int[] nums, int t, int n, int k, int[] bucket){
if(t == n){
// for(var i: bucket) System.out.print(i + " ");
// System.out.println();
for(var i: bucket) if(i != 0) return false;
return true;
}else{
boolean ret = false;
for(var i = 0; i < k; i++){
if(nums[t] <= bucket[i]){
bucket[i] -= nums[t];
boolean tmp = backTrack(nums, t + 1, n, k, bucket);
ret = tmp || ret;
bucket[i] += nums[t];
}
}
return ret;
}
}
public boolean canPartitionKSubsets(int[] nums, int k) {
int sum = 0;
for(var i: nums) sum += i;
if(sum % k != 0) return false;
int[] bucket = new int[k];
int m = sum / k, n = nums.length;
for(var i = 0; i < k; i++){
bucket[i] = m;
}
return backTrack(nums, 0, n, k, bucket);
}
}
但是很遗憾,超大时了。
【优化】下面对这个回溯法进行优化,首先可以先对nums就行排序,这样可以先将大的元素安排好,这样的好处在于用大的元素占据前面的桶之后,我们可以通过if(bucket[i] >= nums[t])这个条件率先进行一些剪枝;另外当t == n的时候其实不需要判断每个bucket是否为0了,因为前面已经对bucket进行平分且有bucket[i] >= nums[t]这个条件,所以最后能到达的一定是符合定义的。
然后这里对int[]类型的数组从大到小排序需要用到stream,具体方法为:nums = Arrays.stream(nums).boxed().sorted((a, b) -> b - a).mapToInt(t -> t).toArray();
class Solution {
public boolean backTrack(int[] nums, int t, int n, int k, int[] bucket){
if(t == n){
// for(var i: bucket) System.out.print(i + " ");
// System.out.println();
// for(var i: bucket) if(i != 0) return false;
return true;
}else{
boolean ret = false;
for(var i = 0; i < k; i++){
if(nums[t] <= bucket[i]){
bucket[i] -= nums[t];
boolean tmp = backTrack(nums, t + 1, n, k, bucket);
if(tmp == true) return true;
ret = tmp || ret;
bucket[i] += nums[t];
}
}
return ret;
}
}
public boolean canPartitionKSubsets(int[] nums, int k) {
int sum = 0;
for(var i: nums) sum += i;
if(sum % k != 0) return false;
int[] bucket = new int[k];
int m = sum / k, n = nums.length;
for(var i = 0; i < k; i++){
bucket[i] = m;
}
nums = Arrays.stream(nums).boxed().sorted((a, b) -> b - a).mapToInt(t -> t).toArray();
return backTrack(nums, 0, n, k, bucket);
}
}
虽然还是超时了,但是已经过了大部分的样例了
【剪枝】我们发现放进每个桶其实这个和顺序是没有关系的,也就是说我们虽然对桶从0-3进行了标号,但是划分的四个子集顺序是没有关系的,但是很明显刚才我们的代码是考虑了顺序的
(5),(1,4),(2,3),(2,3)
以t = 0时4个元素为例子,我们在for循环i的时候,会把4分别放进0-3这三个桶中然后再继续下一层,但是很显然这是没必要的,所以当两个桶的容量一样的时候,我们只需要放进其中一个桶就行了。所以这里加上一个剪枝来把顺序给去掉 if(i != 0 && bucket[i] == bucket[i - 1]) continue;
class Solution {
public boolean backTrack(int[] nums, int t, int n, int k, int[] bucket){
if(t == n){
// for(var i: bucket) System.out.print(i + " ");
// System.out.println();
// for(var i: bucket) if(i != 0) return false;
return true;
}else{
boolean ret = false;
for(var i = 0; i < k; i++){
if(i > 0 && bucket[i] == bucket[i - 1]) continue;
if(nums[t] <= bucket[i]){
bucket[i] -= nums[t];
boolean tmp = backTrack(nums, t + 1, n, k, bucket);
if(tmp == true) return true;
ret = tmp || ret;
bucket[i] += nums[t];
}
}
return ret;
}
}
public boolean canPartitionKSubsets(int[] nums, int k) {
int sum = 0;
for(var i: nums) sum += i;
if(sum % k != 0) return false;
int[] bucket = new int[k];
int m = sum / k, n = nums.length;
for(var i = 0; i < k; i++){
bucket[i] = m;
}
nums = Arrays.stream(nums).boxed().sorted((a, b) -> b - a).mapToInt(t -> t).toArray();
return backTrack(nums, 0, n, k, bucket);
}
}



