从数组中删除任何一个元素后，将奇数大小的数组分成两组相等大小和相同的总和

Question

给定一个奇数大小的数组。您必须从数组中删除任何一个元素，然后查找是否可以将剩余的偶数大小数组分成两组大小相等的元素并且具有相同的元素总和。从数组中删除任何一个元素是强制性的。

Answer 1

所以在这里，我假设有必要从数组中删除1个元素。

请看下面的代码片段。

int solve(int idx, int s, int cntr, int val) { 
if(idx == n) 
    if(cntr != 1) 
     return INT_MAX; 
    else 
     return abs((sum-val)-2*s); 

int ans = INT_MAX; 
if(cntr == 0) 
    ans = min(ans, solve(idx+1, s, cntr+1, arr[idx])); 
else 
    ans = min(ans, min(solve(idx+1,s+arr[idx], cntr, val), solve(idx+1, s, cntr, val))); 
return ans; 
} 

这里sum是原始数组的总和， val是其中U要删除的位置的元素的 值，并且cntr跟踪任何值是否被从阵列或不除去。

所以算法就是这样。

忘记你需要删除任何值，然后问题变成是否可以将数组分成2等份和半。现在我们可以想到这个问题，比如将数组分成2个部分，使得abs(sum-2*sum_of_any_half_part)最小化。所以有了这个想法让我们说我最初有一个桶s它可以是我们所关心的阵列的一部分。因此，在每一步我们都可以将任何元素放入此部分或将其留给其他部分。

现在，如果我们在这个问题中引入删除部分，它只需要一个小的改变。现在在每个步骤而不是2个，你有3个选项。

1. 要删除该特定的元素，然后增加至cntr 1和val到元素的值的数组中的索引处。
2. 不要对此元素做任何事情。这等于将该元素放入其他桶/一半
3. 将该元素放入桶s中，即将s的值增加arr[idx];

现在递归地检查哪个给出了最好的结果。

P.S.查看代码片段中的基本案例以获得更好的想法。

最后如果上面的solve函数给出了ans = 0，那么这意味着是我们可以在删除任何元素之后将数组划分为2个等份部分。

希望这会有所帮助。