配列から任意の1つの要素を削除した後に、奇数サイズの配列を同じサイズと同じ合計の2つの等しいセットに分割します。

Question

奇数サイズの配列が与えられます。配列から任意の要素を削除し、残りの偶数サイズの配列を同じサイズの2つの集合に分割し、それらの要素の合計が同じであるかどうかを調べる必要があります。配列から任意の要素を削除することは必須です。

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; 
} 

sumvalは任意の値をアレイから除去されているか否かを追跡するために uが削除したい任意の位置にある要素の値、及びcntrであり、元の配列の合計であります。

だから、アルゴはこのようになります。

忘れてしまった値を削除してください。そして、問題は、配列を2等分半分に分割することが可能かどうかです。ここでは、配列を2つに分割してabs(sum-2*sum_of_any_half_part)を最小化するなど、この問題を考えることができます。だからこの考えで私は最初にバケツsを持っていて、私たちが心配している配列の一部であると言います。したがって、各ステップで、この要素に要素を配置するか、または他の要素に配置することができます。

ここで、この問題に削除部分を導入すると、そのわずかな変更が必要になります。今度は2つではなく各ステップで3つのオプションがあります。

1. この特定の要素を削除して、アレイ内のそのインデックスの要素の値に1からcntrとvalを増加させます。
2. この要素で何もしないでください。これは、この要素を別のバケット/ハーフに入れることに等しいです。
3. バケットsにこの要素を入れます。つまり、sの値をarr[idx]で増やします。

ここで、最良の結果が得られるかどうかを再帰的に確認します。

P.S.コードスニペットの基本ケースを見て、より良いアイデアを得てください。

最後に上記のsolve関数がans = 0を返すなら、それはyesを意味します。要素を削除した後、配列を2等分部分に分割することができます。

これが役に立ちます。与えられた問題では