組み合わせ (Combinations)

問題

2つの整数 n と k が与えられたとき、範囲 [1, n] から k 個の数値を選択したすべての可能な組み合わせを返す問題である。答えは任意の順序で返すことが可能である。

例

例 1

入力: n = 4, k = 2
出力: [1,2],[1,3],[1,4],[2,3],[2,4],[3,4](/tanakakenji/Rinko/wiki/1,2],[1,3],[1,4],[2,3],[2,4],[3,4)
説明: 4個から2個を選ぶ組み合わせは全部で6つ存在する。
組み合わせは順序付けられていない。つまり、[1,2]と[2,1]は同じ組み合わせとみなされる。

例 2

入力: n = 1, k = 1
出力: [1](/tanakakenji/Rinko/wiki/1)
説明: 1個から1個を選ぶ組み合わせは全部で1つ存在する。

制約

1 <= n <= 20
1 <= k <= n

解答 (Python)

class Solution:
    def combine(self, n: int, k: int) -> list[list[int]]:
        result = []

        def backtrack(start, combination):
            if len(combination) == k:
                result.append(combination.copy())
                return

            for i in range(start, n + 1):
                combination.append(i)
                backtrack(i + 1, combination)
                combination.pop()

        backtrack(1, [])
        return result

解説

初期化

result = []は有効な組み合わせをすべて格納するための空のリストである。

backtrack(start, combination) 関数

これはさまざまな組み合わせを探索する再帰的なヘルパー関数である。

• start: 現在のステップで考慮する開始数値を表す整数。これは重複した組み合わせを避け、各組み合わせ内で数値が昇順に追加されるようにするために使用される。
• combination: 現在構築中の組み合わせを表すリスト。

ベースケース

現在の組み合わせが目的のサイズ kに達した場合（if len(combination) == k）、それは有効な組み合わせとなる。result.append(combination.copy())で現在の組み合わせのコピーをresultリストに追加する。combination.copy()を使用する理由は、同じリストへの参照を追加することを避け、その後のcombinationの変更がresult内の既存のリストに影響を与えることを防ぐためである。

再帰ステップ

1. for i in range(start, n + 1): startからnまでの数値を反復処理する。

2. 以下の操作を順に実行する：

   • combination.append(i): 現在の数値iをcombinationに追加
   • backtrack(i + 1, combination): backtrack関数を再帰的に呼び出し
   • combination.pop(): 再帰呼び出しから戻った後、最後に追加した数値iをcombinationから削除

初期呼び出し

backtrack(1, [])はstart = 1（数値の検討を1から開始）と初期の組み合わせとして空のリスト[]を渡してバックトラック処理を開始する。

重複を避ける仕組み

backtrack関数のstartパラメータは重複した組み合わせを避けるための鍵となる。内部ループをstartから開始することで、各組み合わせ内で数値が常に昇順に追加されるようになる。これにより、[1, 2]のような組み合わせは生成されるが、[2, 1]が別途生成されることを防ぐことができる。