backtracking.all_combinations

In this problem, we want to determine all possible combinations of k numbers out of 1 … n. We use backtracking to solve this problem.

Time complexity: O(C(n,k)) which is O(n choose k) = O((n!/(k! * (n - k)!))),

Attributes

tests

Functions

combination_lists(→ list[list[int]])
create_all_state(→ None)
generate_all_combinations(→ list[list[int]])

Module Contents

backtracking.all_combinations.combination_lists(n: int, k: int) → list[list[int]]

>>> combination_lists(n=4, k=2)
[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

backtracking.all_combinations.create_all_state(increment: int, total_number: int, level: int, current_list: list[int], total_list: list[list[int]]) → None

backtracking.all_combinations.generate_all_combinations(n: int, k: int) → list[list[int]]

>>> 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]]
>>> 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

backtracking.all_combinations.tests