为什么检查多个条件会返回不正确的结果

Question

给定一组整数，是否可以将整数划分为两组，以便一组的总和是10的倍数，而另一组的总和是奇数。每个int必须在一个组或另一个组中。编写一个递归的helper方法，它接受你喜欢的任何参数，并从splitOdd10（）初始调用你的递归帮助器。 （不需要循环。）

这是我的解决方案代码:(是的，我使用了两个辅助方法而不是一个）这就是我试图解决问题的方法:(如果我做错了，请纠正我）。

nums中的每个数字最终只能出现在group1或group2中的一个组中。对于这种情况，元素进入group1 - group1 += nums[start]并以这种方式递归到nums中的每个元素，直到最后一个项目被传递 - 其中索引start超出了nums-start >= nums.length的范围。在这样做之后，我们最终在这个可能性“树”的所有分支的末尾有两组group1和group2。然后检查是否发生了两个组，使得一个组的总和是10的倍数，而其他奇数的总和 - compare(group1, group2)。

我认为，这是我的代码行为不端的地方 - 在致电compare(group1,group2)时。我试试，如果group1是10的倍数和group 2是奇数 - if( a%10 == 0 && b%2 == 1) return true;然后，因为我们不知道反向发生和group1结果是奇数和group2 10的倍数，我检查这也是if( a%2 == 1 && b%10 == 0 ) return true;这没有'适用于所有情况.Here is a screenshot of code output in codingbat.com。但评论compare(group1,group2的第一个条件神奇地修复它.Here is a working code

public boolean splitOdd10(int[] nums) {
 return( splitter(nums,0,0,0) ); 
}
public boolean splitter(int [] nums,int start,  int group1, int group2){
  if (start >= nums.length ) return compare(group1,group2);

  if( splitter(nums,start + 1, group1 += nums[start], group2 ) ) return true; // first condition add element in group1 and recurse on 
  if( splitter(nums,start + 1, group1, group2  += nums[start] ) ) return true;// second condition add element to group2 

  return false;
}

public boolean compare( int a, int b){
  if( a%10 == 0  && b%2 == 1) return true;// <--- if I remove this line the code works
  if( a%2 == 1 && b%10 == 0 ) return true;
  return false;
}

我的问题是：我们如何“知道”检查哪个组是奇数，哪个检查是10的倍数？我检查了两个组的两个条件，但显然这是错误的，并且没有为某些数组返回正确的结果。例如，它为数组[10,0,5,5]返回'true'而不是'false'。请帮助我理解为什么检查这两个条件是不正确的。

Answer 1

从算法上讲，这很容易。

给定一组整数，它们可以总结为奇数或偶数。

• 如果它们总和为奇数，则一个可能的分裂是将所有数字返回到sumIsOdd-bucket，而sumMod10-bucket保持为空。
• 如果它们总和为10的倍数，这是偶数和的一个特例，一个有效的解决方案是将它们全部排序到sumIsMod10-bucket中，而奇数桶保持为空。但是奇数桶是空的，并不总结为奇数，所以这不是解决方案，而是失败。
• 第三种可能性是，总和是偶数，但不能被10整除，那么无论我们多少次从总和中减去10，（甚至没有检查，如果某些数字加起来这样的总和），总和其余的都不会变成奇数，也不会被10整除。例如：36→26→16→6 - 没有休息是奇数，也不能被10整除。
• 最后一种可能性是，我们减去一个偶数和，它本身不能被10整除，一个偶数的和，并把它放入奇数桶中。但是，即使我们在另一个桶中达到可分为10的总和，奇数桶也将是均匀的并且也是失败的。示例：（100,1）可以分为（1）（100），但（101）（）也是一个解决方案。

因此唯一可能的解决方案是总和已经是奇数的情况，并且将所有元素放入奇数桶是有效答案，因为0％10是0。

所以你可以在第一步中将它拆分为一个空的部分，另一侧的整个部分，或者它不可拆分。

一个更复杂的问题是找到两个总和或元素数最小差异的桶。