如果可能，请递归检查以将数组拆分为满足特定条件的两个数组

Question

我正在通过CodingBat解决以下问题：

给定一个整数数组，是否可以将整数分成两组，使一组的和为10的倍数，另一组的和为奇数。每个int必须在一个组或另一个组中。编写一个递归助手方法，该方法接受您喜欢的任何参数，并从splitOdd10（）对递归助手进行初始调用。（不需要循环。）

我在SO上找到了一篇文章，讨论了一个类似的话题：是否有可能将一个数组分成两个具有相等乘积的数组，并尝试通过类比编写代码。这是我迄今为止得到的（Java）：

public boolean splitOdd10(int[] nums) {
    if (nums.length == 0)
    return false;
  else
    return canSplit(0, nums, 0);
}

private boolean canSplit(int first, int[] nums, int term) {
    if (first == nums.length - 1)
    return (term + nums[first]) % 10 == 0 || (term + nums[first]) % 2 == 1;
  else
    return canSplit(first + 1, nums, term + nums[first]);
}

但是在进一步思考代码后，我明白它只是检查原始数组作为一个整体的总和是10的倍数还是奇数。

我很难理解如何从n步进到n-1，以及绑定条件应该是什么，因为这两个数组彼此不依赖，不像它们的乘积相等。

有人能给我一个提示吗？谢谢

Answer 1

我会发布我自己的代码，我相信这更清楚一点（至少对我来说）：

public boolean splitOdd10(int[] nums) {     
  if (nums.length == 0)
    return false;
  else
    return canSplit(0, nums, 0, 0);
}

private boolean canSplit(int index, int[] nums, int mod10Sum, int oddSum) {

  if (index == nums.length)
    return mod10Sum % 10 == 0 && oddSum % 2 == 1;
  else
    return canSplit(index + 1, nums, mod10Sum + nums[index], oddSum)
          || canSplit(index + 1, nums, mod10Sum, oddSum + nums[index]);
}

Answer 2

假设你必须分成两组（A和B）。对于每个元素，您有两个选择：您可以将当前元素放入组A或组B。

状态：mod10（A组模块10中所有元素的总和），odd2（B组模块2中所有元素的总和）

bool check(int arr[], int idx, int mod10, int odd2,  int size){ 

  if(idx == size){

     return (mod10 == 0 and odd2 == 1);
}

   // include current element in group A

  bool first_choice = check(arr, idx + 1, (mod10 + arr[idx]) % 10, odd2, size)

   // include  current element in group B

  bool second_choice = check(arr, idx + 1, mod10, (odd2 + arr[idx]) % 2, size)

  return (first_choice or second_choice);    
}

您可以将这些状态保存在表中，复杂度O（size*10*2）其中size=数组中的总元素