How to Generate Combinations in Python

A combination is a selection of items where order doesn't matter-{A, B} is the same as {B, A}. Python's itertools module provides efficient tools for generating combinations.

Using itertools.combinations

The standard library solution is fast and memory-efficient:

from itertools import combinations

items = ['A', 'B', 'C', 'D']

# All pairs (2-combinations)
pairs = list(combinations(items, 2))
print(pairs)
# [('A', 'B'), ('A', 'C'), ('A', 'D'), ('B', 'C'), ('B', 'D'), ('C', 'D')]

# All triplets (3-combinations)
triplets = list(combinations(items, 3))
print(triplets)
# [('A', 'B', 'C'), ('A', 'B', 'D'), ('A', 'C', 'D'), ('B', 'C', 'D')]

The function returns an iterator, so wrap with list() only when needed.

Combinations with Replacement

Allow elements to repeat using combinations_with_replacement:

from itertools import combinations_with_replacement

items = ['A', 'B', 'C']

# Can pick same element multiple times
result = list(combinations_with_replacement(items, 2))
print(result)
# [('A', 'A'), ('A', 'B'), ('A', 'C'), ('B', 'B'), ('B', 'C'), ('C', 'C')]

Practical Examples

Finding All Subsets of Size k

from itertools import combinations

def subsets_of_size(items, k):
    """Generate all subsets of exactly size k."""
    return [set(combo) for combo in combinations(items, k)]

print(subsets_of_size([1, 2, 3, 4], 2))
# [{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}]

Team Pairing

from itertools import combinations

players = ["Alice", "Bob", "Charlie", "Diana"]

# Generate all possible pairs
for player1, player2 in combinations(players, 2):
    print(f"{player1} vs {player2}")

Output:

Alice vs Bob
Alice vs Charlie
Alice vs Diana
Bob vs Charlie
Bob vs Diana
Charlie vs Diana

Sum Combinations

from itertools import combinations

numbers = [1, 2, 3, 4, 5]
target = 7

# Find all pairs that sum to target
pairs = [(a, b) for a, b in combinations(numbers, 2) if a + b == target]
print(pairs)

Output:

[(2, 5), (3, 4)]

Manual Implementation (Educational)

Understanding the recursive approach helps in interviews:

def generate_combinations(items, r):
    """Generate combinations using pick/skip recursion."""
    if r == 0:
        return [[]]
    if not items:
        return []
    
    first, rest = items[0], items[1:]
    
    # Include first element (need r-1 more)
    with_first = [[first] + combo for combo in generate_combinations(rest, r - 1)]
    
    # Exclude first element (still need r)
    without_first = generate_combinations(rest, r)
    
    return with_first + without_first

print(generate_combinations(['A', 'B', 'C'], 2))

Output:

[['A', 'B'], ['A', 'C'], ['B', 'C']]

note

The recursive approach uses the "pick or skip" pattern: for each element, either include it in the combination or skip it, then recurse on the remaining elements.

Iterative Implementation

Avoid recursion limits with an iterative approach:

def combinations_iterative(items, r):
    """Generate combinations iteratively using indices."""
    n = len(items)
    if r > n:
        return []
    
    indices = list(range(r))
    result = [tuple(items[i] for i in indices)]
    
    while True:
        # Find rightmost index that can be incremented
        for i in range(r - 1, -1, -1):
            if indices[i] != i + n - r:
                break
        else:
            return result
        
        indices[i] += 1
        for j in range(i + 1, r):
            indices[j] = indices[j - 1] + 1
        
        result.append(tuple(items[i] for i in indices))
    
    return result

Counting Combinations

Calculate how many combinations exist without generating them:

from math import comb  # Python 3.8+

# C(n, r) = n! / (r! * (n-r)!)
print(comb(5, 2))  # 10 combinations of 5 items taken 2 at a time
print(comb(10, 3)) # 120 combinations

# For older Python versions
from math import factorial

def count_combinations(n, r):
    return factorial(n) // (factorial(r) * factorial(n - r))

Output:

10
120

tip

Use math.comb() to check feasibility before generating large combination sets. Generating all combinations of 20 items taken 10 at a time produces 184,756 results.

All Possible Subset Sizes

Generate combinations of all sizes (power set excluding empty set):

from itertools import combinations

def all_combinations(items):
    """Generate combinations of all sizes."""
    result = []
    for r in range(1, len(items) + 1):
        result.extend(combinations(items, r))
    return result

print(all_combinations(['A', 'B', 'C']))

Output:

[('A',), ('B',), ('C',), ('A', 'B'), ('A', 'C'), ('B', 'C'), ('A', 'B', 'C')]

Combinations vs Permutations

Concept	Order Matters?	[A,B] vs [B,A]	Function
Combination	No	Same	combinations()
Permutation	Yes	Different	permutations()

from itertools import combinations, permutations

items = ['A', 'B', 'C']

print(list(combinations(items, 2)))
# [('A', 'B'), ('A', 'C'), ('B', 'C')]  # 3 results

print(list(permutations(items, 2)))
# [('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B')]  # 6 results

Performance Comparison

Method	Speed	Memory	Stack Safe
itertools.combinations	⚡ C-optimized	Low (iterator)	✅ Yes
Recursive	🐢 Slow	High	❌ Risk
Iterative	Medium	High	✅ Yes

Summary

Use itertools.combinations() for production code-it's fast, memory-efficient, and handles edge cases.

• The recursive "pick or skip" implementation is useful for understanding the algorithm and coding interviews.
• For combinations with repeated elements, use combinations_with_replacement().