長さnの配列を1からn（繰り返しなし）で2つの等和に分割するアルゴリズム

長さがNの配列を与え、配列内の数値には1〜Nを繰り返しません。あなたは配列が等しい合計のリストに分割できるかどうかを確認する必要があります。長さnの配列を1からn（繰り返しなし）で2つの等和に分割するアルゴリズム

時間の複雑さがある部分集合和問題を使って解くことができます。時間の複雑さを減らすためのアルゴリズムはありますか？

出典

2017-02-09 Suresh Arora

あなたは1つの事を配列のすべての要素を合計し、0以外の値がない場合は2を割ります –

リストは連続している必要がありますか？私はあなたがサブアレイまたはサブシーケンスを探しているのですか？ –

リストは連続している必要はないので、基本的にサブシーケンス –

お客様の要件に応じて、配列には常に1からNの数字が含まれていると結論づけます。したがってif Array.Sum()==Even答えはYESです。

出典

2017-02-09 12:23:05 apomene

1からnまでの要素の合計がn*(n+1)/2に等しいので、あなたはn*(n+1)はnが4の倍数である、又はn+1場合は4の倍数であるかどうかをチェックと等価である4の倍数であるかどうかを確認しなければなりません。その複雑さはO（1）です。この条件を満たす場合、2つのサブセットは次のようになります。

nが4の倍数である場合：前半の奇数と後半の偶数を合計し、奇数の前半の偶数後半にはもう片方が。例えば、1 3 5 8 10 12、および2 4 6 7 9 11 11

n = 3の場合4：ほぼ同じこと、最初の3つを片手で1と2、3つを3つに分割するもう1つ、4のサイズ倍数を持つ残りのセリフがあります。例：1 2 4 7、3 5 6;またはもしあなたが好きなら、3 4 7と1 2 5 6

出典

2017-02-09 18:29:55

長さnの配列を1からn（繰り返しなし）で2つの等和に分割するアルゴリズム

答えて

関連する問題