k個の整数が与えられた集合内のxまで加算されるかどうかをチェックするアルゴリズムを設計します。

n個の整数と整数xのセットが与えられます。 k個の整数が与えられた集合のxに足りるかどうかをチェックするアルゴリズムを設計できますか？複雑さはO（N ^（K-1）* LOGN）配列 k個の整数が与えられた集合内のxまで加算されるかどうかをチェックするアルゴリズムを設計します。

がため

（それらの全てのN ^（K-1））k個の番号の組み合わせを取る

2012-01-27 user973931

質問には通常、少なくとも1つの疑問符が含まれています。 –

@TimCooper - よく彼らは急いでいる、彼らは今インタビューで自分のiPhoneにこれを掲示している！ –

'Array'の' permutation'関数を試してみてください。 – itdoesntwork

最終複雑：O（N ^（K-1）* LOGN）

十分なスペース（n ^（k/2））がある場合は、O（n ^（k/2）logアレイ。

計算合計はO（1）です。これは、以前の組み合わせに対して行った計算を再利用できるためです。（a + b + c + d） - （a + b + c + e）=（a + b + c + d）

2012-01-27 23:35:56 ElKamina

そして 'sum（combination） 'はどうやって見つけられますか？それは 'O（n）'時間を取って複雑さをO（n ^（k-1）* n）に上げていないでしょうか？また、私はステップ2を信じます。「... k-1ナンバーの...」という意味です。 – quasiverse

最後に、 'n ^（k-1）'の組み合わせがありますか？私は彼らのkを選ぶと信じていると私は彼らがどのように等しいのか分からない。 – quasiverse

@quasiverse ... nCk-1は user973931

答えて