如何证明代码中递归“搜索”算法的正确性？
我不知道如何证明这个问题的递归算法。我不能用数学归纳法来解决这个证明。(虽然我对数学归纳很熟悉)。
问题是：
给定一个整数数组、num和一个正整数k，找出是否有可能将该数组划分为和都相等的k非空子集。
示例1：
输入：nums = [4, 3, 2, 3, 5, 2, 1]，k = 4输出：True解释:可以用相等和将它划分为4个子集(5)、(1，4)、(2,3)、(2,3)。
注意：
1 <= k <= len(Num) <= 16.0< numsi < 10000.
算法(https://leetcode.com/problems/partition-to-k-equal-sum-subsets/solution/)
我第一次尝试时，i = 0在第一次递归，groups[i] = v，我必须判断搜索(组，行，名词，目标)。然而，在这个时候，我不知道如何思考返回值的真假会影响什么。
class Solution {
public boolean search(int[] groups, int row, int[] nums, int target) {
if (row < 0) return true;
int v = nums[row--];
for (int i = 0; i < groups.length; i++) {
if (groups[i] + v <= target) {
groups[i] += v;
if (search(groups, row, nums, target)) return true;
groups[i] -= v;
}
if (groups[i] == 0) break;
}
return false;
}
public boolean canPartitionKSubsets(int[] nums, int k) {
int sum = Arrays.stream(nums).sum();
if (sum % k > 0) return false;
int target = sum / k;
Arrays.sort(nums);
int row = nums.length - 1;
if (nums[row] > target) return false;
while (row >= 0 && nums[row] == target) {
row--;
k--;
}
return search(new int[k], row, nums, target);
}
}回答 2
Stack Overflow用户
发布于 2019-09-17 14:14:29
方法canPartitionKSubsets首先计算所有数字的和sum。如果分区存在，那么每个分区中的元素之和必须是target = sum//k。他们检查sum是否可以被k整除。
他们检查最后一个数字是否大于target。如果是的话，那么这个号码不可能出现在任何一个群体中。因此，在这种情况下，它们返回false。
现在轮到搜索电话了。但让我们弄清楚变量的解释。在每次对search的调用中，变量groups表示当前考虑添加到每个k组中的数字之和。变量row表示当前认为要添加到其中一个组中的数字的原始列表中的位置。
在search内部，循环所有将row位置中的数字添加到每个k组的情况。它添加它，并递归地尝试搜索是否是这样一个完整的解决方案。如果没有，则将其从添加的组中移回。
这些组试图按顺序填充列表中的数字，说明从组0到组编号k-1。
当它们到达当前有零和的组时，就会中断循环。这是算法中的一个错误。你写的那份声明。这一步只是为了切断一些循环，但它只有在假设所有的数字都是正的情况下才有意义，至少在你的转录中是没有给出的。如果问题允许非正数，只需将该行从代码中删除即可。
该算法的工作原理很简单，因为它尝试了所有的情况。如果您安排了将列表中的一些数字放入树中的一些k组中的所有可能性，首先将任何数字作为根放置，然后每次放置额外的数字时分支，则树节点与堆栈调用相同，树的叶子是放置所有数字的排列方式。该算法是在树上进行深度优先搜索，但行除外。
if (groups[i] == 0) break;这是不对的问题，正如所述。
Stack Overflow用户
发布于 2019-09-18 00:40:42
在阅读了上面的想法后，我跌倒了。如我们所知，行表示当前认为要添加到其中一个组中的数字的原始列表中的位置。如果行< 0，我们将得到在group.The中添加的所有数字，尝试将v放在适当的组中。并且for循环底部的组至少有一个元素，因为所有组都可以看作是一个集合。如果这个组不能包含一个元素，另一个元素也不能。如果当前组不适合v，则尝试下一个组。
注:问题限制num[i> 0 ]。请参阅我编辑的问题中的注意事项。1 <= k <= len(Num) <= 16.0< numsi < 10000.
https://stackoverflow.com/questions/57973908
复制相似问题
腾讯云开发者
