fucking-algorithm
fucking-algorithm copied to clipboard
labuladong
经典回溯算法：集合划分问题 :: labuladong的算法小抄
东哥能帮我看看我这个为什么会超时么? 我觉得定义一个有返回值的backtrack不太好理解,我就尝试了这个void的backtrack, 但是数据量大的时候就超时了
class Solution {
boolean possibility = false;
public boolean canPartitionKSubsets(int[] nums, int k) {
// 对于每一个数字,可能进入到 第 1-k 个分组中的一个
// 也就是说 需要遍历每一个数字, 然后每一个数字都可以进入k个分组中的一个
// 生成 k 个 分组
int[] group = new int[k];
// 对于平均的和进行求解
int sum = 0;
for(int x: nums) sum+=x;
int target = sum/k;
backtrack(0, nums, target, group);
return possibility;
}
public void backtrack(int i, int[] nums, int target, int[] group){ // 对所有的对象进行遍历
if(possibility) return; // 如果有可能,那么不需要再往下检查了
if(i==nums.length){ // 当所有的对象都已经尝试过各自的可能以后
for(int x: group){
if(x != target) return ; // 检查到不可能的组合,返回
}
possibility = true; // 如果执行到这,说明有可能
return ; //返回
}
// 对于每一个数字对象,都可以选择进入k个分组中的某一个,此时也就是每一个对象遍历所有的可能
for(int k=0; k<group.length; k++){
if(group[k] + nums[i] > target){ // 如果当前的group加上此时的nums都已经大于target了,那么说明不合适
continue;
}
// 开始做选择
group[k] += nums[i];
// 去递归
backtrack(i+1, nums, target, group);
// 中间可以判断possibility,如果为true直接return即可
if(possibility) return ;
// 撤销选择
group[k] -= nums[i];
}
}
}
@luckywords @0xlightyear 我用的C语言，遍历数字解法，不对nums排序85/155时间超限，降序后155/150时间超限😭
@luckywords @0xlightyear @Qiqiqiqiqishuo 可能是力扣测试用例更新了，之前的代码确实可能超时。我在文章中更新了优化的方案，通过备忘录和位图技巧进一步提高算法的效率。
for (int i = 0; i < bucket.length; i++) {
// 剪枝，桶装装满了
if (bucket[i] + nums[index] > target) {
continue;
}
// 将 nums[index] 装入 bucket[i]
bucket[i] += nums[index];
// 递归穷举下一个数字的选择
if (backtrack(nums, index + 1, bucket, target)) {
return true;
}
// 撤销选择
bucket[i] -= nums[index];
//剪枝
if(bucket[i] == 0) break;
}
添加最后一个剪枝，就能不超时了
if(bucket[i] == 0) break;这个剪枝我感觉像是int[] nums里面的某一个数循环了一圈都没有找到合适的数去配队凑成target，所以后面的都不用在看了，必定凑不成题目说的那种。 例：nums[0] = 7, target = 8,现在bucket[]里面只放了一个7，循环了一遍nums数组，发现找不到1，然后撤销选择bucket[i] -= nums[index]; 这时bucket[i]=0，所以直接break。 不知道理解的对不对
// 用@zhao2019010704大佬的方式加工的
public boolean helper(int[] bucket, int target, int[] nums, int index) {
// base case，index来记录当前循环到第几个数据了
if(index == nums.length) {
// nums[]遍历完了，这时候说明所有数都找到了桶，如果没找到的话会在bucket[i] == 0被剪掉
return true;
}
// 穷举 nums[index] 可能装入的桶
for(int i = 0; i < bucket.length; i++) {
if(bucket[i] + nums[index] > target) {
continue;
}
// 装进去
bucket[i] += nums[index];
if(help(bucket, target, nums, index + 1)) {
return true;
}
// 到这里说明上面没有return,修建
bucket[i] -= nums[index];
// 这里可能index还没到nums.length，但是出现了无法凑成target的数，所以直接返回break，然后fasle就行
if(bucket[i] == 0) {
// nums[index]找不到可以凑成target的数
break;
}
}
return false;
}
boolean backtrack(int k, int bucket,
...
/*
if (k == 0) {
return true;
}*/
/*用 k==1 来进行判断也是可以的，因为除了最后一个桶没有确定外，其他的桶都确定了其中的数字（桶中数字的和等于target），那么还没有被添加到桶中的数字必定会被添加到最后一个桶中，因此就不需要在额外判断
*/
if(k==1) return true;
...
根据大佬们的剪枝和解释，再+一个剪枝 if(nums[0]>target) return false; 对于已经降序排序的数组，如果第一个数字就比目标数字大，那肯定是凑不齐了，举例nums=[7,6,4,1],k=3,target=sum/k=6.
位运算不熟练的同学，可以用bitset 嘿嘿
class Solution {
public:
bool canPartitionKSubsets(vector<int> &nums, int k) {
typedef bitset<20> bs20;
if (k > nums.size())return false;
int sum = 0;
for (int i: nums)sum += i;
if (sum % k)return false;
int target = sum / k;
//最大的数比target大
if(nums[0]>target)return false;
unordered_set<bs20> memo;
sort(nums.begin(), nums.end(), greater<int>());
function<bool(int, int, bs20)> backtrack = [&](int at, int sum, bs20 used) {
if (memo.count(used))return false;
if (at == k) {
return true;
}
if (sum == target) {
return backtrack(at + 1, 0, used);
} else {
for (int i = 0; i < nums.size(); i++) {
if (used[i])continue;
if (sum + nums[i] > target)continue;
sum += nums[i];
used[i] = 1;
if (backtrack(at, sum, used)) {
return true;
} else {
//记录失败情况
memo.insert(used);
}
sum -= nums[i];
used[i] = 0;
//没有能够凑成target
if(sum==0)break;
}
}
return false;
};
return backtrack(0, 0, 0);
}
};
if(bucket[i] == 0) break; 个人理解是：当前的桶经过上面的试探后无法满足条件，桶还是空的，所以后面的桶也不用试了，不可能满足条件，所以直接返回false。不知道这样理解对不对呢？
贴一个解法，增加两种剪枝，第二种剪枝不怎么用，只有在数组中具有大量和target相等的数时才有用。
class Solution:
def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
total_sum = sum(nums)
if total_sum % k != 0:
return False
self.target = total_sum // k
nums = sorted(nums, reverse=True)
if nums[0] > self.target:
return False
# start, end = -1, -1
# for i,v in enumerate(nums):
# if v == self.target:
# if start == -1:
# start = i
# end = i
# else:
# end = i
# elif v < self.target:
# break
# if start != -1:
# nums = nums[:start]+nums[end+1:]
# k = k-(end-start+1)
self.nums = nums
self.k = k
self.used = 0
self.mem = dict() # 备忘录，避免不同子集的相同组合数（因为这题关注的每个子集组合数的总和，不需要关心子集的顺序）
return self.DFS(0, 0, 0)
def DFS(self, k, cur, start):
if k == self.k:
return True
if self.target == cur:
res = self.DFS(k+1, 0, 0)
self.mem[self.used] = res
return res
if self.used in self.mem:
return self.mem[self.used]
for i in range(len(self.nums)):
if cur + self.nums[i] > self.target:
continue
if ((self.used>>i) & 1) == 1:
continue
self.used |= 1<<i
cur += self.nums[i]
if self.DFS(k, cur, i+1):
return True
cur -= self.nums[i]
self.used ^= 1<<i
return False
通俗来说，我们应该尽量「少量多次」，就是说宁可多做几次选择，也不要给太大的选择空间；宁可「二选一」选 k 次，也不要 「k 选一」选一次。
这里有个疑问，这里的“「二选一」选 k 次”是在桶的视角，我感觉应该是"「二选一」选 n 次"？
各位大佬，问一个十分愚笨的问题为什么
if (backtrack(nums, index + 1, bucket, target)) {
return true;
}
不能直接写成这样
backtrack(nums, index + 1, bucket, target)
直接递归为什么不行
@labuladong 东哥，第一种解法在for循环里加入剪枝
if(i > 0 && bucket[i] == bucket[i-1]){
continue;
}
效率会急剧提高
第一种的减枝优化
class Solution {
private:
vector<int> sums;
bool backtrace(vector<int>&nums,int idx,int target){
if(idx == nums.size()){
for(int i = 0;i < sums.size();i++){
if(sums[i] != target){
return false;
}
}
return true;
}
unordered_set<int> st;
for(int i = 0;i < sums.size();i++){
if(sums[i] + nums[idx] > target){
continue;
}
if(st.count(sums[i])){
continue;
}
sums[i] += nums[idx];
if(backtrace(nums,idx+1,target)){
return true;
}
sums[i] -= nums[idx];
st.insert(sums[i]);
}
return false;
}
public:
bool canPartitionKSubsets(vector<int>& nums, int k) {
sums.resize(k);
sort(nums.rbegin(),nums.rend());
if(k > nums.size()){
return false;
}
int sum = accumulate(nums.begin(),nums.end(),0);
if(sum % k != 0){
return false;
}
count = k;
return backtrace(nums,0,sum/k);
}
};
额，我突然发现，其实因为剪纸
if (bucket[i] + nums[index] > target) {
continue;
}
basecase其实可以直接返回true的
第二种是不是可以这样：
if (i == 0) break; // 因为第一个元素一定要放到第一个桶里 // 撤销选择 used[i] = false; ...
我这个版本的暴力回溯为啥只需4ms？这离超时还差的远吧。 执行用时： 4 ms, 在所有 Java 提交中击败了75.53%的用户 内存消耗： 39.5 MB, 在所有 Java 提交中击败了38.43%的用户 通过测试用例： 162 / 162
public class Solution698 {
/**
* 从数组中任意取N个数凑成target装入桶k之中。
* 思路：nums已从小到达排序，我们从后向前取数组中的数组，看能否凑成整数target。
* 不能从小到大凑整的原因是：前面N个小数组成target后，后面剩余的数太大导致不能再凑成target了。
* 从大到小凑数能尽可能大数和小数1比1搭配。
*
* @param k 桶的序号
* @param bucket 桶k内已装入的数
* @param nums 可装入的数的数组
* @param start 从start查找前面的数 -- Arrays.sort(nums)逆序太麻烦，所以这里从后向前查找。
* @param target 需要凑成的目标数
* @return true 能组成 false不能组成
*/
boolean backtrack(int k, int bucket, int[] nums, int start, boolean[] selected, int target) {
if (k == 0) {
return true;
}
// 当前桶装满了，装入下一个桶
if (bucket == target) {
return backtrack(k - 1, 0, nums, nums.length - 1, selected, target);
}
for (int i = start; i >= 0; i--) {
// start位置的数没有选过并且小于target余数时可以选择
if (selected[i] || nums[i] > target - bucket) {
continue;
}
selected[i] = true;
if (backtrack(k, bucket + nums[i], nums, i - 1, selected, target)) {
return true;
}
selected[i] = false;
// 当测试到当前num[i]不可用时，快速剪枝之前与之相同的数
while (i > 0 && nums[i - 1] == nums[i]) {
i--;
}
}
return false;
}
/**
* 输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4
* 输出： True
* 说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。
*/
public boolean canPartitionKSubsets(int[] nums, int k) {
if (k == 1) {
return true;
}
int sum = 0;
for (int num : nums) {
sum += num;
}
if (sum % k > 0) {
return false;
}
int avg = sum / k;
// 从小到大排序
Arrays.sort(nums);
// 如果最大的数已经超过的平均数，则无法平分
if (nums[nums.length - 1] > avg) {
return false;
}
boolean[] selected = new boolean[nums.length];
return backtrack(k, 0, nums, nums.length - 1, selected, avg);
}
public static void main(String[] args) {
Solution698 solution = new Solution698();
System.out.println(solution.canPartitionKSubsets(new int[] { 4, 5, 9, 3, 10, 2, 10, 7, 10, 8, 5, 9, 4, 6, 4, 9 }, 5));
}
}
if (bucket[i] == 0) return false; //我感觉是这样的：首先这个意思就是如果当前桶装下这个数字是false且当前桶是空桶，就直接对前面的选择返回false.
//解释 : 在把数字往每一个桶中装时是优先装前面的桶(序号的大小顺序), 只有前面的桶不能装了之后，才会选择装序号靠后的桶，所以如果 序号为 i 的桶是空桶，那么序号靠后的桶在这个时候肯定也都是空桶.针对以上前提，如果当前 i 桶 装下这个数字为 false, 那么同理后面的桶装下这个数字也会是false,也就是说，针对前面 index - 1 个数字对前面 i - 1 个桶的选择，会导致 index 当前这个数字在后面的桶中没有桶可装. 因此可直接针对前面的选择返回false.
