问题:
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 this additional constraint: If a value in the array is chosen to be in the group, the value immediately following it in the array must not be chosen.
For eg:-
groupNoAdj(0, {2, 5, 10, 4}, 12) → true
groupNoAdj(0, {2, 5, 10, 4}, 14) → false
groupNoAdj(0, {2, 5, 10, 4}, 7) → false
正如您在最后一个案例中看到的那样,虽然存在子集 {2,5},其总和为目标值“7”,但它们是相邻值,因此不能一起选择。 还有一个条件是不能使用局部变量。
我想出了以下解决方案:
public boolean groupNoAdj(int start, int[] nums, int target) {
if(start==nums.length)
return target==0;
if(start==nums.length-1&&!(target==0))
return (target-nums[start]==0);
if(target==0)
return true;
if((start<nums.length-1)&&groupNoAdj(start+1, nums, target-nums[start]))
return groupNoAdj(start+2, nums, target-nums[start]);
return groupNoAdj(start+1, nums, target);
}
但在 groupNoAdj(0, {2, 5, 10, 4, 2}, 7) 的情况下它会失败它在实际应该返回 true 时返回 false
在这种情况下无法真正找出导致它失败的原因。
最佳答案
你在上一个条件中遗漏了一些东西:
public static void main(String[] args) {
int[] arr1 ={2, 5, 10, 4};
int[] arr2 = {2, 5, 10, 4};
System.out.println(groupNoAdj(0, arr1, 12)); // prints true
System.out.println(groupNoAdj(0, arr2, 7)); // prints false
}
public static boolean groupNoAdj(int start, int[] nums, int target) {
if(target == 0)
return true;
if(start == nums.length)
return target==0;
if(start == nums.length-1)
return target-nums[start] == 0;
return
groupNoAdj(start+2, nums, target-nums[start]) || // either pick the "current" item (and skip the "next")
groupNoAdj(start+1, nums, target); // or don't pick it
}
关于java - 确定整数数组中是否存在在几个条件下总和为给定目标值的子集,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/24837157/