Introduction

Generating all combinations of a string means enumerating every subset of its characters where order does not matter. That is different from permutations, where rearranging the same characters creates a different result. The standard algorithm is recursive backtracking, though iterative bitmasking is also useful for compact implementations.

Understand the Output

For the string "ABC", the combinations are:

• '""'
• '"A"'
• '"B"'
• '"C"'
• '"AB"'
• '"AC"'
• '"BC"'
• '"ABC"'

Notice that "AB" and "BA" are not separate results. Once order stops mattering, the count becomes 2^n for a string of length n, including the empty combination.

Recursive Backtracking

The clearest algorithm makes two decisions for each character:

• include it
• skip it

1def combinations(s: str) -> list[str]:
2    result = []
3
4    def backtrack(index: int, current: list[str]) -> None:
5        if index == len(s):
6            result.append("".join(current))
7            return
8
9        current.append(s[index])
10        backtrack(index + 1, current)
11        current.pop()
12
13        backtrack(index + 1, current)
14
15    backtrack(0, [])
16    return result
17
18print(combinations("ABC"))

This works because each character contributes one binary choice. The recursion tree naturally covers all subsets.

Generate Only Combinations of Size k

Many real problems need only combinations of a specific length. In that case, generate only what you need instead of building every subset first.

1def combinations_of_length(s: str, k: int) -> list[str]:
2    result = []
3
4    def backtrack(start: int, current: list[str]) -> None:
5        if len(current) == k:
6            result.append("".join(current))
7            return
8
9        for i in range(start, len(s)):
10            current.append(s[i])
11            backtrack(i + 1, current)
12            current.pop()
13
14    backtrack(0, [])
15    return result
16
17print(combinations_of_length("ABCDE", 3))

This is often the better form for search and optimization problems.

Bitmask Enumeration

An iterative alternative is to use a bitmask. Each bit tells you whether the corresponding character is present in the combination.

1def combinations_bitmask(s: str) -> list[str]:
2    result = []
3    n = len(s)
4
5    for mask in range(1 << n):
6        chars = []
7        for i in range(n):
8            if mask & (1 << i):
9                chars.append(s[i])
10        result.append("".join(chars))
11
12    return result
13
14print(combinations_bitmask("ABC"))

This approach is compact and works well when you already think in terms of subset states.

Handle Duplicate Characters Carefully

If the input contains repeated characters, naive generation can produce duplicate outputs. For example, "AAB" can generate "A" more than once.

One simple solution is to deduplicate with a set:

1def unique_combinations(s: str) -> list[str]:
2    result = set()
3
4    def backtrack(index: int, current: list[str]) -> None:
5        if index == len(s):
6            result.add("".join(current))
7            return
8
9        current.append(s[index])
10        backtrack(index + 1, current)
11        current.pop()
12
13        backtrack(index + 1, current)
14
15    backtrack(0, [])
16    return sorted(result)
17
18print(unique_combinations("AAB"))

That is easy to understand, though skipping duplicates during generation can be more efficient for large inputs.

Complexity and Practical Limits

All-combinations generation is exponential by definition. A length-20 string already has more than one million combinations. That means the algorithm is correct but still impractical for large inputs unless you restrict the combination size or consume the results lazily.

If you only need size-k combinations, generate exactly those rather than all subsets.

Standard Library Option in Python

If you need combinations of fixed length, the standard library is often the best answer.

1from itertools import combinations
2
3for combo in combinations("ABCDE", 2):
4    print("".join(combo))

This avoids reimplementing a common tool and yields values lazily.

Common Pitfalls

The most common mistake is confusing combinations with permutations. If order does not matter, generating all reorderings does extra work and produces the wrong result set.

Another issue is ignoring the exponential growth of the output. Even a clean algorithm becomes impractical once the string length grows.

Duplicate characters are another source of bugs. If the string can repeat letters, deduplication rules must be part of the design.

Summary

• Combinations are subsets, so order does not create new results.
• Recursive backtracking is the clearest general algorithm.
• Generate only size-k combinations when that is all you need.
• Bitmask enumeration is a compact iterative alternative.
• Expect exponential growth and handle duplicate characters deliberately.