java - 子集逻辑，跳过所有其他元素

Question

给定一个整数数组，是否可以选择一组某些整数，使得该组总和达到给定的目标，并具有以下附加约束:如果选择数组中的某个值在该组中，则不得选择数组中紧随其后的值。 (不需要循环。)

groupNoAdj(0, [2, 5, 10, 4], 12) → true

groupNoAdj(0, [2, 5, 10, 4], 14) → false

groupNoAdj(0, [2, 5, 10, 4], 7) → false

我想知道是否还有什么需要补充的，不太确定错误在哪里:

public boolean groupNoAdj(int start, int[] nums, int target) {
    if (start == nums.length) {return (target == 0);}

    if (groupNoAdj(start + 1, nums, target - nums[start])){
    return true;
  }

    if (groupNoAdj(start + 1, nums, target)){
      return (groupNoAdj(start + 1, nums, target));
    } 

    return false;
}

Answer 1

这是对代码的修改:

public boolean groupNoAdj(int start, int[] nums, int target) {

        if (start >= nums.length) {return (target == 0);}  //neded to change to '>=' because start can go over length of array 

//in your code you return true when the two following numbers from array are chosen, which is contrary to the requirement of the task 
        if (groupNoAdj(start + 2, nums, target - nums[start])){ 
            return true;
        }

        if (groupNoAdj(start + 1, nums, target)){
            return true;
        } 

        return false;
    }

这是全新的代码，例如，对于输入(数组 = [1,2,3,4,5] 和目标 99)，仅递归调用函数 groupNoAdj 12 次，而不是 25 次。

    public boolean groupNoAdj(int start, int[] nums, int target) {
        if(target - nums[start] == 0) // there is no need let 'start' be greater than the lenghth of nums' array 
            return true;

  //doing what in the previous code but I am not letting to call function with start greater than the length of nums' array
        if (!(start + 2 >= nums.length) && groupNoAdj(start + 2, nums, target - nums[start])){
            return true;
        } 

        if (!(start + 1 == nums.length) && groupNoAdj(start + 1, nums, target)){
            return true;
        }

        return false;
    }      

此递归背后的逻辑:我正在检查数组列表中所有可能的和(我假设一个数字也是和)，但两个数字彼此“相邻”的情况除外。 如果您对此代码有任何疑问，请询问。 解决这个问题没有什么秘诀，你必须简单地练习，练习，再练习，你就会知道如何解决这个问题。