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

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

Method 1: Using combinations_with_replacement() (Recommended)

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

tip

This is the most efficient and Pythonic approach. The function is implemented in C under the hood, making it significantly faster than any pure-Python alternative. Always prefer this method unless you have a specific reason to implement the logic manually.

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

caution

This method generates N^K total tuples before filtering, which is far more than the final result. For N=10, K=5, this produces 100,000 tuples just to keep 2,002 unique combinations. Use combinations_with_replacement() instead for any non-trivial input.

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

note

The key insight is that each inner loop starts from the current value of the outer loop variable (for example, range(i, N), range(j, N)), ensuring non-decreasing order and eliminating duplicates. However, this approach requires hardcoding a loop for each level of K, making it impractical for variable or large K values.

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

# Wrong: combinations() does not allow repetition
result = list(combinations(range(N), K))
print(result)

Output:

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

note

Notice that tuples like (0, 0, 0), (0, 0, 1), and (1, 1, 2) are missing because combinations() picks each element at most once.

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

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

# Benchmark product + filtering
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).