子集逻辑，跳过每隔一个元素

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），它仅递归调用函数组 NoAdj 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;
    }      

这种递归背后的逻辑：我正在检查数组列表中所有可能的总和（我假设一个数字也是总和），除了两个数字彼此"相邻"的情况。如果您对此代码有任何疑问，请询问。解决这个问题不是秘诀，你必须只是简单的练习，练习和练习更多，你会看到如何解决这个问题。