從數組中刪除任何一個元素後，將奇數大小的數組分成兩組相等大小和相同的總和

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個等份部分。

希望這會有所幫助。