組み合わせ和Ⅱ

40.組み合わせ和Ⅱ

難易度: 中

トピック: 配列、バックトラッキング

候補番号 (candidates) とターゲット番号 (target) のコレクションが与えられた場合、候補番号の合計がターゲットになる、候補内のすべての一意の組み合わせを見つけます。

候補内の各数字は、組み合わせで 1 回のみ使用できます。

注: ソリューション セットには重複した組み合わせが含まれていてはなりません。

例 1:

• 入力: 候補 = [10,1,2,7,6,1,5]、ターゲット = 8
• 出力: [[1,1,6], [1,2,5], [1,7], [2,6]]

例 2:

• 入力: 候補 = [2,5,2,1,2]、ターゲット = 5
• 出力: [[1,2,2], [5]]

制約:

• 1
• 1
• 1

解決策:

後戻りアプローチを使用できます。重要なアイデアは、まず配列を並べ替えて重複を簡単に処理し、次にバックトラッキングを使用して可能なすべての組み合わせを探索することです。

このソリューションを PHP で実装してみましょう: 40.組み合わせ和Ⅱ

説明：

1. 並べ替え: 重複を簡単に処理し、組み合わせが並べ替えられた順序で形成されるようにするために、候補配列が並べ替えられます。
2. バックトラック: バックトラック機能は、考えられるすべての組み合わせを探索するために使用されます。
   • ターゲットがゼロになった場合は、現在の組み合わせを結果に追加します。
   • 現在のインデックスから始めて候補を反復処理します。候補が前の候補と同じ場合は、重複した組み合わせを避けるためにスキップします。
   • ターゲットから現在の候補を減算し、新しいターゲットと次のインデックスを使用してバックトラック関数を再帰的に呼び出します。
   • 再帰呼び出しは、有効な組み合わせが見つかるか、すべての可能性がなくなるまで続きます。
3. 枝刈り: 候補が目標を超える場合、さらなる候補も目標を超えるため、ループから早期に抜け出します。

このコードは、各候補が各組み合わせで 1 回だけ使用されることを保証しながら、合計がターゲットとなる一意の組み合わせをすべて出力します。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

以上が組み合わせ和Ⅱの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。