java - 确定整数数组中是否存在在几个条件下总和为给定目标值的子集

Question

问题:

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

在这种情况下无法真正找出导致它失败的原因。

Answer 1

你在上一个条件中遗漏了一些东西:

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
}