您的解决方案给出了误报。例如,数组{2,8}
不能分成两个积相等的子数组,但你会返回true
,因为 2*8 的平方根是 4。
当您尝试解决此类递归问题时,您应该尝试思考如果将输入大小减少 1 会发生什么。
假设给定一个数组arr
具有有效的分割(分成两个具有相同乘积的子组)。这意味着如果删除第一个元素a[0]
,您必须能够将数组的其余部分分成两个子组,以便p1 == p2 * a[0]
or p1 == p2 / a[0]
, where p1
是第一组元素的乘积,p2
是第二组元素的乘积。
这表明递归方法应该检查输入数组的给定尾部(即 arr[from]...arr[arr.length-1] 对于某些 from >= 0)是否存在分成两组,例如第一组的乘积除以第二组的乘积(反之亦然)等于给定因子:
public static boolean canSplit(int[] arr, int from, double factor)
{
if (from == arr.length - 1) {
return arr[from] == factor;
}
return canSplit(arr, from + 1, factor * arr[from]) || canSplit(arr, from + 1, factor / arr[from]);
}
初始调用将是:
public static boolean canSplit(int[] arr)
{
if (arr.length < 2) {
return false;
} else {
return canSplit(arr, 0, 1); // the second parameter is 0, since the first recursive call
// applies to the whole array
// the third parameter is 1, since we want to check if there
// are two groups such that the product of the first divided
// by the product of the second is 1 (i.e. the two products
// are equal)
}
}
Tests:
System.out.println (canSplit(new int[]{2,15,3,4,2,5}));
System.out.println (canSplit(new int[]{2,4,6,2,3,4}));
System.out.println (canSplit(new int[]{2,2,4}));
System.out.println (canSplit(new int[]{2,8}));
Output:
true
false
true
false