在 GFG 上的 Partition Equal Subset sum 中得到错误的答案

Question

我正在尝试解决 partition equal subset problem on GFG. I am aware of the correct way of doing this via reducing it to the subset sum problem。但是，我想到了另一种方法，但我无法弄清楚它有什么问题。

我维护了两个总和变量：partition1 和 partition2，在每次递归调用时，所考虑的元素都可以转到其中一个。我正在检查两者的总和是否随时相等，如果是，我 return 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;

可能会使函数 return 过早地变为 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);
}

在 GFG 上的 Partition Equal Subset sum 中得到错误的答案

Getting wrong answer in Partition Equal Subset sum on GFG

c++

arrays

algorithm

dynamic-programming