Function generate_all_combinations

backtracking/all_combinations.py:23–61

Generates all possible combinations of k numbers out of 1 ... n using backtracking. >>> generate_all_combinations(n=4, k=2) [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]] >>> generate_all_combinations(n=0, k=0) [[]] >>> generate_all_combinations(n=10, k=-1) Traceback

(n: int, k: int)

def generate_all_combinations(n: int, k: int) -> list[list[int]]:
    """
    Generates all possible combinations of k numbers out of 1 ... n using backtracking.

    >>> generate_all_combinations(n=4, k=2)
    [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
    >>> generate_all_combinations(n=0, k=0)
    [[]]
    >>> generate_all_combinations(n=10, k=-1)
    Traceback (most recent call last):
        ...
    ValueError: k must not be negative
    >>> generate_all_combinations(n=-1, k=10)
    Traceback (most recent call last):
        ...
    ValueError: n must not be negative
    >>> generate_all_combinations(n=5, k=4)
    [[1, 2, 3, 4], [1, 2, 3, 5], [1, 2, 4, 5], [1, 3, 4, 5], [2, 3, 4, 5]]
    >>> generate_all_combinations(n=3, k=3)
    [[1, 2, 3]]
    >>> generate_all_combinations(n=3, k=1)
    [[1], [2], [3]]
    >>> generate_all_combinations(n=1, k=0)
    [[]]
    >>> generate_all_combinations(n=1, k=1)
    [[1]]
    >>> from itertools import combinations
    >>> all(generate_all_combinations(n, k) == combination_lists(n, k)
    ...     for n in range(1, 6) for k in range(1, 6))
    True
    """
    if k < 0:
        raise ValueError("k must not be negative")
    if n < 0:
        raise ValueError("n must not be negative")

    result: list[list[int]] = []
    create_all_state(1, n, k, [], result)
    return result


def create_all_state(