问题是关于 finding if there exists a subset in an array of ints that sums to a target with following tweaks
- 必须包含所有 5 的倍数。
- 如果 1 后跟 5 的倍数,则不得包含该 1。
有一个
Standard solution
/*
* Given an array of ints, is it possible to choose a group of some of the ints,
* such that the group sums to the given target with these additional constraints:
* all multiples of 5 in the array must be included in the group.
* If the value immediately following a multiple of 5 is 1,
* it must not be chosen. (No loops needed.)
*
* groupSum5(0, {2, 5, 10, 4}, 19) → true
* groupSum5(0, {2, 5, 10, 4}, 17) → true
* groupSum5(0, {2, 5, 10, 4}, 12) → false
* groupSum5(0, {3, 5, 1}, 9) → false
* groupSum5(0, {2, 5, 4, 10}, 12) → false
* groupSum5(0, {3, 5, 1}, 5) → true
* groupSum5(0, {1, 3, 5}, 5) → true
* groupSum5(0, {1}, 1) → true
*/
public boolean groupSum5(int start, int[] nums, int target) {
if (start >= nums.length) return (target == 0);
if (nums[start] % 5 == 0) {
if (start < nums.length - 1 && nums[start + 1] == 1){
return groupSum5(start + 2, nums, target - nums[start]);
}
return groupSum5(start + 1, nums, target- nums[start]);
}
return groupSum5(start + 1, nums, target - nums[start])
|| groupSum5(start + 1, nums, target);
}
My Approach
public boolean groupSum5(int start, int[] nums, int target) {
final int len = nums.length;
if (start == len) {
return target == 0;
}
if (start > 0 && nums[start] == 1 && (nums[start- 1] % 5) == 0 ) {
return groupSum5(start + 1, nums, target);
}
if (groupSum5(start + 1, nums, target - nums[start])) {
return true;
} if ((nums[start] % 5) != 0
& groupSum5(start + 1, nums, target)) {
return true;
}
return false;
}
就时间复杂度而言,上述 2 种方法中哪一种更好?
如果我没有记错的话,标准解决方案或第一个解决方案的复杂度大于指数(3^n)? 我想如果我们考虑递归调用,复杂度是 (4^n) 是否正确?
最佳答案
我认为你的代码是错误的。 groupSum5(0, [0, 1, 1], 1) 在您的代码中返回 false,因为两个 1 都被排除。在最坏的情况下,正确的 groupSum5 和你的都是 O(2^n) 。尽管 groupSum5 在第一段代码中出现了 4 次,但在单个堆栈帧中只有 2 个调用可能发生
关于java - 具有一些额外条件的子集和算法的复杂性,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/61266892/