1からKまでの全ての数字が配列からの数字を使ってのみ形成できるかどうかを調べる

Question

私の問題は次のとおりです：N個の整数とKの配列を与えました。 1からKまで、与えられた配列からの要素しか使用できないようにします。要素を複数回使用することはできません。

ここでは、配列= {1,2,3,4}とK = 10の例を示しています。答えは、すべて1 = 1,2 = 2,3 = 4 + 3 + 1,10 = 4 + 3 + 2 + 1、8 = 4 + 3 + 1,9 = 4 + 3 + 1,10 = 1。

ここで別の例があります：array = {1,3,4} and K = 3、整数2を作ることができないので、答えはFALSEです。

私はインターネット上で1つのコードを見つけましたが、私はそれを考えていましたが、どのように動作するのか、それはいつも正しいのですか？ここで

は私のコードです：https://code.google.com/codejam/contest/4244486/dashboard#s=p2&a=2

分析：

int n, k; cin>>n>>k; 
int arr[n]; 
for(int i=0;i<n;i++) { 
    cin>>arr[i]; 
} 
sort(arr,arr+n); 
int sum=0; 
for(int i=0;i<n;i++) { 
    if(arr[i]>sum+1) return false; 
    sum+=arr[i]; 
    if(sum>=k) return true; 
} 
return true; 

Answer 1

これは、リンク2015年からGoogle Codeのジャムのシンプルな問題であり、そのアルゴリズムの背後にあるhttps://code.google.com/codejam/contest/4244486/dashboard#s=a&a=2

ロジックは次のとおりです。

整数を維持しながら最小の数値から反復します。sumsumは、0 to sumからすべての数値を生成できることを意味します。

我々は0 to sumから数字を作り、そして今、新しい番号に出会うことができた場合、arr[2]言って、我々が0 to sumからのすべての数字を作成することができますので、我々は（sumからsum + arr[2]にすべての数字を作成することができることは明らかであり、我々は単純に追加することができますsumとsum + arr[2]間の任意の数を作るために、それらの小さい合計のいずれかにarr[2]。

（コードif(arr[i]>sum+1) return false;この線によって示される）任意の間隙がある場合はそれはARRの間に商品のない組み合わせを意味する[0]、ARR [1- 1]は、arr[i]の助けを借りても合計+1になる可能性があります。ケースインポイントarr[] = {1,3,4}. k = 3。

最初の反復後、0 to 1から任意の数値を作成できます。 2回目の繰り返しではarr[1] = 3で、sum and arr[i]の間に隙間があることがわかります。つまり、これらの数値をどのように追加しても、必要なギャップを埋めることができないため、関数はfalseを返します。