java - 核心 Java 编程中的 groupNoAdjacency 递归问题

Question

我有以下问题，这次我做了一些研发并得出了解决方案，但解决方案中也存在一个故障(一种情况)。

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

groupNoAdj(0, {2, 5, 10, 4}, 12) => true --> This is true coz of 2+10 =12,NoAdjacency    
groupNoAdj(0, {2, 5, 10, 4}, 14) => false -> 10+4=14,numbers are adjacent,its false    
groupNoAdj(0, {2, 5, 10, 4}, 7) => false  --> 2+5=7,numbers are adjacent,its false    

我的解决方案如下。它适用于除一种场景之外的所有以下给定场景。

<小时/>

代码:

public boolean groupNoAdj(int start, int[] numbers, int target) {    
       start=0;    
       boolean[] reached = new boolean[target+1];         
       reached[0] = true;            
          for (int i=0;i<numbers.length;i++){    
               for (int j = i + 2; j<numbers.length; j++){    
                  if(numbers[j] + numbers[i] == target){      
                      reached[target]=true;          
                  }else if(numbers[j] + numbers[i] < target){    
                      numbers[i] = numbers[j] + numbers[i];    
                  }     
            }          
       }            
      return reached[target];      
 }     

下面给出了场景

                          Expected This Run   
groupNoAdj(0, {2, 5, 10, 4}, 12) → true true OK      
groupNoAdj(0, {2, 5, 10, 4}, 14) → false false OK      
groupNoAdj(0, {2, 5, 10, 4}, 7) → false false OK      
groupNoAdj(0, {2, 5, 10, 4, 2}, 7) → true true OK      
groupNoAdj(0, {2, 5, 10, 4}, 9) → true true OK      
groupNoAdj(0, {10, 2, 2, 3, 3}, 15) → true true OK      
groupNoAdj(0, {10, 2, 2, 3, 3}, 7) → false false OK      
groupNoAdj(0, {}, 0) → true true OK      
**groupNoAdj(0, {1}, 1) → true false X**      
groupNoAdj(0, {9}, 1) → false false OK      
groupNoAdj(0, {9}, 0) → true true OK      
groupNoAdj(0, {5, 10, 4, 1}, 11) → true true OK 

我的代码不适用于粗体标记的代码。您想提供任何想法、输入或建议。我已尝试分析代码，但由于我没有获得特殊情况的解决方案，因此我将其发布在 Stackoverflow 中.

Answer 1

public boolean groupNoAdj(int start, int[] nums, int target) {
   if (target == 0)
   return true;
   if (start < nums.length)
   return groupNoAdj(start + 2,nums,target - nums[start]) || groupNoAdj(start + 1,nums,target);
   return false;
}