サイズnの有限の数値セットがあるとします。
質問： Iの要素の合計がJの要素の合計以下である場合に、組み合わせIが組み合わせJに先行するように、そのセットのk-組み合わせを列挙するための効率的なアルゴリズムはありますか？
明らかに、組み合わせを単純に列挙し、それらの合計に従って並べ替えることが可能です。ただし、セットが大きい場合は、並べ替えはもちろん、すべての組み合わせを野蛮に列挙することはできません。合計でランク付けされた最初のm<<Choose（n、k）の組み合わせのみを取得することに関心がある場合、宇宙の熱的死の前にそれらを取得することは可能ですか？
この方法で集合を列挙するための多項式アルゴリズムはありません（P = NPでない限り）。
そのようなアルゴリズムがあれば（Aとしましょう）、部分和問題を多項式で解くことができます。
ステップ1は多項式で実行され（仮定）、ステップ2はで実行されることに注意してくださいO(log(2^n)) = O(n)。
結論：部分和問題はNP完全であるため、この問題を効率的に解くとP = NPであることが証明されます。したがって、この問題に対する既知の多項式解はありません。
編集：問題はNP困難ですが、「最小の」mサブセットを取得O(n+2^m)するには、最小mの要素を選択し、これらの要素からすべてのサブセットを生成し、それらmの最小mのものを選択します。したがって、-の値がかなり小さい場合は、mそれを計算することが可能かもしれません。