"""
p37 — Combinations (LeetCode 77, MEDIUM).

Implementations:
    combine        — start-index backtracking + pruning bound.
    combine_naive  — same template without pruning (for comparison).
    combine_brute  — itertools.combinations oracle.

Run: python3 solution.py
"""
from __future__ import annotations
import itertools
import random
from typing import List


# --------------------------------------------------------------------------------------
# Pruned: max starting value at this level is n - need + 1, where need = k - len(path).
# Loop upper bound (exclusive) is therefore (n - need + 1) + 1 = n - need + 2.
# --------------------------------------------------------------------------------------
def combine(n: int, k: int) -> List[List[int]]:
    result: List[List[int]] = []
    path: List[int] = []

    def backtrack(start: int) -> None:
        if len(path) == k:
            result.append(path[:])
            return
        need = k - len(path)
        # INVARIANT: i must leave at least (need - 1) values above it in [i+1..n].
        # Hence i_max = n - need + 1; range upper bound = i_max + 1.
        upper = n - need + 2
        for i in range(start, upper):
            path.append(i)
            backtrack(i + 1)
            path.pop()

    backtrack(1)
    return result


def combine_naive(n: int, k: int) -> List[List[int]]:
    result: List[List[int]] = []
    path: List[int] = []

    def backtrack(start: int) -> None:
        if len(path) == k:
            result.append(path[:])
            return
        for i in range(start, n + 1):
            path.append(i)
            backtrack(i + 1)
            path.pop()

    backtrack(1)
    return result


def combine_brute(n: int, k: int) -> List[List[int]]:
    return [list(c) for c in itertools.combinations(range(1, n + 1), k)]


def _canon(combos: List[List[int]]) -> List[tuple]:
    return sorted(tuple(c) for c in combos)


# --------------------------------------------------------------------------------------
# Tests
# --------------------------------------------------------------------------------------
def edge_cases() -> None:
    # k=0 → one combination: the empty one
    assert combine(5, 0) == [[]]
    assert combine_naive(5, 0) == [[]]

    # k=n → exactly one
    assert combine(4, 4) == [[1, 2, 3, 4]]

    # n=1, k=1
    assert combine(1, 1) == [[1]]

    # Canonical example
    expected_4_2 = [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
    assert combine(4, 2) == expected_4_2
    assert _canon(combine_naive(4, 2)) == _canon(expected_4_2)

    # Sizes match Pascal
    from math import comb
    for n in range(7):
        for k in range(n + 1):
            assert len(combine(n, k)) == comb(n, k), f"n={n} k={k}"
            assert len(combine_naive(n, k)) == comb(n, k), f"n={n} k={k}"

    # Each combination strictly increasing (canonical form)
    for c in combine(6, 3):
        assert c == sorted(c) and len(set(c)) == len(c)

    print("edge_cases: PASS")


def stress_test() -> None:
    rng = random.Random(42)
    for _ in range(200):
        n = rng.randint(0, 8)
        k = rng.randint(0, n)
        oracle = _canon(combine_brute(n, k))
        assert _canon(combine(n, k)) == oracle, f"combine disagrees on n={n} k={k}"
        assert _canon(combine_naive(n, k)) == oracle, f"combine_naive disagrees on n={n} k={k}"
    print("stress_test: 200 random (n, k) — pruned and naive both agree with itertools.combinations.")


if __name__ == "__main__":
    edge_cases()
    stress_test()
    print("ALL TESTS PASSED")