在GFG上的分区等子集和中得到错误答案

Question

我正在尝试解决GFG上的分区等子集问题。我知道将其简化为子集和问题的正确方法。然而，我想到了另一种方法，我不知道它出了什么问题

我维护了两个sum变量：partition1和partition2，在每次递归调用时，所考虑的元素都可以转到其中的任何一个。我正在检查两个总和是否在任何时候都相等，如果是，我返回1。这是我的相同代码：

int traverse(int N,int arr[],int partition1,int partition2, int curr){

if(partition1==partition2 and partition1!=0)
return 1;


if(curr>=N)
return 0;

//cout<<partition1<<" "<<partition2<<endl;    
return traverse(N,arr,partition1+arr[curr],partition2,curr+1) or traverse(N,arr,partition1,partition2+arr[curr],curr+1);
}

目前，我只关心复发，而不是将其转换为DP解决方案的最佳方法，因为即使对于这个输入，它也给出了错误的答案：

9(元件数量(

75 131 977 305 220 957 47 56 840(输入阵列(

预期的输出是NO，但我的代码给出的输出是YES。有人能帮我弄清楚这个解决方案出了什么问题吗？

Answer 1

您的if语句：

if(partition1==partition2 and partition1!=0)
return 1;

可能会使函数过早返回1，因为在遍历所有数字之前，partition1仍然可以等于partition2。以下对代码的修改解决了问题：

int traverse(int N, int arr[], int partition1, int partition2, int curr) {
if (curr >= N)
return partition1 == partition2 && partition1 != 0;

return traverse(N, arr, partition1 + arr[curr], partition2, curr + 1) || traverse(N, arr, partition1, partition2 + arr[curr], curr + 1);
}