公式解説には以下のようなコードが載っており、なぜこれで \(O(\binom{N}{K}\min(K, N - K))\) になるのか疑問に思うかもしれません。 この計算量解析は自明ではないと考えています。

def func(x: list[int], i: int):
    if len(x) == K:
        # 長さが K であるようなインデックスの列 x がここで列挙される
        return
    if i == N:
        return
    func(x, i + 1)
    func(x + [i], i + 1)

func([], 0)

公式解説にある工夫で \(K \le \frac{N}{2}\) となっていることを前提にすると、実はこの関数が呼び出される回数は合計で \(O\left(K\binom{N}{K}\right)\) 回です。以下はこのことの証明となります。

この関数の呼び出しは \(2\) つに分けられます

• \(\mathrm{len}(x) = K\) であるような呼び出し(=4行目でreturnされる呼び出し)
• それ以外の呼び出し

前者が合計でちょうど \(\binom{N}{K}\) 回なのはよいでしょう。
後者の呼び出しのうち、引数のiが\(i\) であるようなものは、\(0, 1, 2, \dots, i-1\) の \(i\) 個の数から \(K\) 個未満選ぶ方法の数だけあります(そして、\(K\) 個未満選ぶ実際の選び方がそれぞれ引数のxに入って呼び出されます)。よって呼び出し回数の合計は \(\displaystyle \sum_{i = 0}^{N} \sum_{k = 0}^{\min(i, K - 1)} \binom{i}{k} = \sum_{k = 0}^{K - 1} \sum_{i = k}^N \binom{i}{k}\) となります。

ここで、\(\displaystyle \sum_{i = k}^N \binom{i}{k} = \binom{N + 1}{k + 1}\) です。\(N + 1\) 人から \(k + 1\) 人選ぶときに、最も番号の若い \(1\) 人で場合分けすると左辺の和が出てきます。

結局後者の呼び出し回数は \(\displaystyle \sum_{k = 0}^{K - 1} \binom{N + 1}{k + 1} = \sum_{k = 1}^{K} \binom{N + 1}{k} = \sum_{k = 1}^{K} \left(\binom{N}{k} + \binom{N}{k - 1}\right) \le 2\sum_{k = 1}^{K} \binom{N}{k} \le 2K\binom{N}{K}\) となります。(範囲外の二項係数は \(0\) とします)

なお、同じようでも以下のようなコードでは同様の解析で計算量は \(\displaystyle\sum_{k = 1}^{\color{red}{K}+1} \binom{N + 1}{k}\) となりTLEします。(\((N, K) = (10^6, 1)\) のときなど)

def func(x: list[int], i: int):
    if i == N:
        if len(x) == K:
            # 長さが K であるようなインデックスの列 x がここで列挙される
        return
    func(x, i + 1)
    if len(x) < K: func(x + [i], i + 1)

func([], 0)