子集和问题代码错误排查：分割等和子集测试用例不通过

嘿，我来帮你找出代码里的问题！你的代码在处理小规模测试用例时正常，但遇到稍大的用例就出错，核心问题出在数组越界访问和初始化逻辑的条件覆盖错误上，咱们一步步拆解：

代码中的关键错误 #

1. 数组越界访问 #

在check函数的双重循环里，你没有区分边界情况和正常逻辑：当i=0的时候，代码依然会执行if(a[i-1]<=j)的判断——此时i-1=-1，访问a[-1]属于非法的数组越界操作。这种行为是未定义的，小测试用例可能刚好没触发内存错误，但大一点的用例就会破坏计算逻辑，导致错误结果。

2. 初始化逻辑的条件覆盖问题 #

你原来的三个if是独立执行的，比如当i>=1且j>=1时，代码没有跳过初始化的判断，而是会先执行前面的if(i==0)和if(j==0)（当然这两个条件不成立），但关键是当i=0时，即使j=0被设为true，后续的a[i-1]访问还是会执行，直接导致越界。

修正后的代码 #

我调整了循环内的条件结构，确保边界情况和正常逻辑互斥，避免越界访问：

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
#define ll long long

bool check(int a[], int n, int s) {
    bool dp[n+1][s+1];
    for(int i=0;i<n+1;i++) {
        for(int j=0;j<s+1;j++) {
            // 边界情况：没有元素时，只有和为0才能达成
            if(i == 0) {
                dp[i][j] = (j == 0);
            }
            // 边界情况：和为0时，空子集即可满足
            else if(j == 0) {
                dp[i][j] = true;
            }
            // 正常逻辑：判断是否选取当前元素
            else {
                if(a[i-1] <= j) {
                    dp[i][j] = dp[i-1][j - a[i-1]] || dp[i-1][j];
                } else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
    }
    return dp[n][s];
}

int main() {
    int t;
    cin>>t;
    while(t--) {
        int n;
        cin>>n;
        int arr[n];
        int s=0;
        for(int i=0;i<n;i++){
            cin>>arr[i];
            s+=arr[i];
        }
        if(s%2==0) {
            s/=2;
            if(check(arr,n,s))
                cout<<"YES\n";
            else
                cout<<"NO\n";
        } else
            cout<<"NO\n";
    }
    return 0;
}

修正说明 #

• 改用if-else if-else的分层结构，确保每一轮循环只执行一种情况的逻辑，不会重复覆盖或执行非法操作。
• 当i=0时，直接通过j==0判断赋值，完全避开了数组访问。
• 只有当i>=1且j>=1时，才会访问a[i-1]，此时i-1的范围是0~n-1，属于数组的合法索引，彻底解决越界问题。

现在测试你提到的8 479 758 315 472 730 101 460 619用例，总和是3934，一半为1967，修正后的代码可以正确计算出存在符合条件的子集，输出YES。

内容的提问来源于stack exchange，提问作者PRAJWAL BHAGAT