Skip to content
Tutorial Reference

How to Generate All Unique K-Size Combinations up to N in Python

Learn how to efficiently generate all unique K-length combinations with replacement from a range of N values in Python using built-in functions and custom approaches.

When working with combinatorics in Python, a common task is generating all unique combinations of a given size K using elements from a range of numbers 0 to N-1, where repetition is allowed but order does not matter. For example, (0, 1, 2) and (2, 1, 0) are considered the same combination and should appear only once.

This type of operation, known as combinations with replacement, is useful in mathematical modeling, probability calculations, data science feature generation, and algorithm design.

In this guide, you will learn multiple ways to generate these combinations in Python, from the most efficient built-in solution to manual approaches, with clear explanations of when to use each.

Understanding the Problem

Given two integers:

  • N: the range of values (0 to N-1)
  • K: the size of each combination

Generate all unique K-size tuples where:

  • Each element is in the range [0, N-1]
  • Elements within a tuple are in non-decreasing order (to ensure uniqueness)
  • Repetition is allowed (e.g., (0, 0, 1) is valid)

Examples:

N = 2, K = 3 → [(0,0,0), (0,0,1), (0,1,1), (1,1,1)]
N = 4, K = 2 → [(0,0), (0,1), (0,2), (0,3), (1,1), (1,2), (1,3), (2,2), (2,3), (3,3)]

Python's itertools module provides combinations_with_replacement(), which is purpose-built for exactly this task. It generates all K-length subsequences of elements from the input iterable, allowing individual elements to be repeated.

from itertools import combinations_with_replacement

N = 4
K = 3

result = list(combinations_with_replacement(range(N), K))

print(f"Total combinations: {len(result)}")
print("Combinations:", result)

Output:

Total combinations: 20
Combinations: [(0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 0, 3), (0, 1, 1), (0, 1, 2), (0, 1, 3), (0, 2, 2), (0, 2, 3), (0, 3, 3), (1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 2, 2), (1, 2, 3), (1, 3, 3), (2, 2, 2), (2, 2, 3), (2, 3, 3), (3, 3, 3)]

How Many Combinations Are There?

The number of K-size combinations with replacement from N elements is given by the formula:

C(N + K - 1, K) = (N + K - 1)! / (K! × (N - 1)!)
from math import comb

N, K = 4, 3
total = comb(N + K - 1, K)
print(f"Expected combinations: {total}")  # 20

Output:

Expected combinations: 20

Method 2: Using product() with Duplicate Filtering

This approach first generates all possible K-length tuples (including different orderings) using itertools.product(), then filters out duplicates by sorting each tuple and keeping only unique sorted versions.

from itertools import product

N = 4
K = 3

all_tuples = product(range(N), repeat=K)

seen = {}
for tup in all_tuples:
    key = tuple(sorted(tup))
    seen.setdefault(key, None)

result = list(seen.keys())

print(f"Total combinations: {len(result)}")
print("Combinations:", result)

Output:

Total combinations: 20
Combinations: [(0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 0, 3), (0, 1, 1), (0, 1, 2), (0, 1, 3), (0, 2, 2), (0, 2, 3), (0, 3, 3), (1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 2, 2), (1, 2, 3), (1, 3, 3), (2, 2, 2), (2, 2, 3), (2, 3, 3), (3, 3, 3)]

Method 3: Using Recursive Generation

A recursive approach builds combinations element by element, ensuring each new element is greater than or equal to the previous one:

def unique_combinations(N, K, start=0, current=None):
    """Recursively generate all unique K-size combinations from range(N)."""
    if current is None:
        current = []

    if len(current) == K:
        yield tuple(current)
        return

    for i in range(start, N):
        yield from unique_combinations(N, K, start=i, current=current + [i])


N = 4
K = 3

result = list(unique_combinations(N, K))

print(f"Total combinations: {len(result)}")
print("Combinations:", result)

Output:

Total combinations: 20
Combinations: [(0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 0, 3), (0, 1, 1), (0, 1, 2), (0, 1, 3), (0, 2, 2), (0, 2, 3), (0, 3, 3), (1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 2, 2), (1, 2, 3), (1, 3, 3), (2, 2, 2), (2, 2, 3), (2, 3, 3), (3, 3, 3)]

This approach is educational and gives you full control over the generation process. It only generates valid combinations (no wasted work), but the Python function call overhead makes it slower than the C-implemented combinations_with_replacement().

Method 4: Using Nested Loops (Fixed K Only)

For a fixed, small value of K, you can use nested loops directly. This is the most explicit approach but is not generalizable: the number of loops must match K.

Example for K = 3

N = 4
K = 3

result = []
for i in range(N):
    for j in range(i, N):
        for k in range(j, N):
            result.append((i, j, k))

print(f"Total combinations: {len(result)}")
print("Combinations:", result)

Output:

Total combinations: 20
Combinations: [(0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 0, 3), (0, 1, 1), (0, 1, 2), (0, 1, 3), (0, 2, 2), (0, 2, 3), (0, 3, 3), (1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 2, 2), (1, 2, 3), (1, 3, 3), (2, 2, 2), (2, 2, 3), (2, 3, 3), (3, 3, 3)]

Example for K = 2

N = 4

result = []
for i in range(N):
    for j in range(i, N):
        result.append((i, j))

print("Combinations:", result)

Output:

Combinations: [(0, 0), (0, 1), (0, 2), (0, 3), (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)]

Common Mistake: Using combinations() Instead of combinations_with_replacement()

A frequent error is using itertools.combinations(), which does not allow repeated elements:

from itertools import combinations

N = 4
K = 3

result = list(combinations(range(N), K))
print(result)

Output:

[(0, 1, 2), (0, 1, 3), (0, 2, 3), (1, 2, 3)]

Correct: use combinations_with_replacement()

from itertools import combinations_with_replacement

N = 4
K = 3

result = list(combinations_with_replacement(range(N), K))
print(f"Total: {len(result)}")  # 20 (not 4)

Performance Comparison

Method Time Complexity Space Complexity Generalizable Best For
combinations_with_replacement() O(C(N+K-1, K)) O(1) per item ✅ Yes All use cases (recommended)
product() + filtering O(N^K) O(N^K) ✅ Yes Educational purposes only
Recursive generation O(C(N+K-1, K)) O(K) call stack ✅ Yes Custom generation logic
Nested loops O(C(N+K-1, K)) O(1) per item ❌ Fixed K only Small, fixed K values 
import timeit
from itertools import combinations_with_replacement, product

N, K = 10, 5

t1 = timeit.timeit(
    lambda: list(combinations_with_replacement(range(N), K)),
    number=1000
)

def product_method():
    seen = {}
    for tup in product(range(N), repeat=K):
        seen.setdefault(tuple(sorted(tup)), None)
    return list(seen.keys())

t2 = timeit.timeit(product_method, number=1000)

print(f"combinations_with_replacement: {t1:.4f}s")
print(f"product + filtering:           {t2:.4f}s")
print(f"Speedup: {t2/t1:.1f}x faster")

Output (approximate):

combinations_with_replacement: 0.0798s
product + filtering:           45.7539s
Speedup: 573.0x faster

Summary

Generating all unique K-size combinations with replacement from a range of N values is a common combinatorics task. Key takeaways:

  • Always prefer itertools.combinations_with_replacement(): it is the fastest, most readable, and most Pythonic solution.
  • Use nested loops only when K is small and fixed (2 or 3), and you want explicit, simple code.
  • Use the recursive approach when you need custom logic during generation (for example, filtering or early termination).
  • Avoid product() + filtering for anything beyond small inputs, as it generates exponentially more tuples than needed.
  • Don't confuse combinations() (no repetition) with combinations_with_replacement() (repetition allowed).
Navigation