私は他のみんなと同じようにこの問題に苦しんでおり、この問題を説明するのに十分な数の投稿があると確信しています. ただし、それを完全に理解するという点では、サブセットサムの問題に関連して、ここにいるすべての偉大な人々から私の考えを共有し、より効率的な解決策を得たいと思いました.
インターネットで検索しましたが、実際には多くの情報源がありますが、完全に理解するために、アルゴリズムを再実装するか、独自のアルゴリズムを見つけたいと思っています.
私が苦労している重要なことは、セットのサイズが大きくなることを考慮した効率です。(制限はありません。概念的に大きいだけです)。私がアイデアを実装しようとしている 2 つのフェーズは、与えられた整数Tに等しい2 つの数値を見つけ、3 つの数値を見つけ、最終的にKの数値を見つけることです。私が持っているいくつかのアイデア;
2 つの整数部分については、基本的に配列O(nlogn)をソートし、配列内の各要素についてその負の値を検索しています。(つまり、配列要素が-3を検索する3の場合)。要素にインデックスを付けるO(1)を提供することで、ハッシュ テーブルを含める方がよいのではないでしょうか?
3 つ以上の整数については、すばらしいブログ投稿を見つけました。ただし、著者自身でさえ、多数には適用できないと述べています。
したがって、サブセットの問題にどのようなアイデアを適用できるかを2と3 およびそれ以上の整数にしました。大きな入力に対しても効率的な動的計画法を設定するのに苦労しています。