バックトラッキングによる組み合わせ生成の完全解説
組み合わせアルゴリズム（Combination Algorithm）は、与えられた範囲 [1, n] から
k
個の要素を選ぶすべての組み合わせを生成するアルゴリズムです。
バックトラッキング手法を用いることで、効率的に全組み合わせを列挙できます。
from typing import List
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
"""
Return all possible combinations of k numbers out of range [1..n].
Args:
n (int): Upper bound of range (inclusive).
k (int): Size of each combination.
Returns:
List[List[int]]: All combinations.
Time Complexity: O(C(n, k))
Space Complexity: O(k) for recursion depth
"""
result: List[List[int]] = []
path: List[int] = []
def backtrack(start: int) -> None:
# ベースケース: 目標サイズに到達
if len(path) == k:
result.append(path.copy())
return
# 現在の開始位置から n まで試行
for i in range(start, n + 1):
path.append(i) # 選択
backtrack(i + 1) # 再帰
path.pop() # バックトラック
backtrack(1)
return result
# 使用例
solution = Solution()
result = solution.combine(4, 2)
print(f"C(4,2) = {result}")
# Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]時間計算量 O(C(n,k)): 生成される組み合わせの数に比例します。 各組み合わせの生成に O(k) 時間かかるため、全体では O(k × C(n,k)) となりますが、 通常は O(C(n,k)) で表現されます。
空間計算量 O(k): 再帰スタックの深さが最大 k であり、 path 配列も最大 k 要素を保持するため、O(k) の空間を使用します。