Introduction

Finding combinations from an array is a classic task in search, testing, recommendation, and feature engineering. The best approach depends on whether you need all combination sizes or only size k, and whether memory is limited. Combination counts grow rapidly, so algorithm choice must include output-size reality.

Clarify the Exact Combination Problem

Before implementation, define these requirements:

• combinations of fixed size k or all sizes
• combinations with or without duplicate input values
• order-insensitive combinations or order-sensitive permutations
• streaming output or full materialization

A lot of bugs come from solving permutations when combinations were required.

Count Growth and Complexity

For fixed size k, number of combinations is n choose k. For all non-empty sizes, total combinations are 2^n - 1. This growth dominates runtime regardless of language.

Practical implication:

• small arrays can materialize all combinations safely
• medium arrays should often stream combinations
• large arrays require pruning, sampling, or constraints

No implementation can avoid output-size cost once all combinations are requested.

That is why "best way" usually means "best way for the expected size and downstream use." A mathematically elegant algorithm still becomes impractical if the calling code insists on materializing millions of combinations at once.

Python Best Practice with itertools

For Python, itertools.combinations is usually the cleanest and fastest approach.

1from itertools import combinations
2
3items = ["A", "B", "C", "D"]
4
5pairs = list(combinations(items, 2))
6print(pairs)
7
8# stream without full list allocation
9for combo in combinations(items, 3):
10    print(combo)

Use generator iteration when you do not need full list in memory.

Generate All Sizes

If you need all non-empty combinations, chain over k values.

1from itertools import combinations
2
3
4def all_combinations(items):
5    for k in range(1, len(items) + 1):
6        for combo in combinations(items, k):
7            yield combo
8
9for c in all_combinations([1, 2, 3]):
10    print(c)

This remains memory-efficient because results are yielded lazily.

Recursive Strategy for Languages Without Built-Ins

In Java or C-like languages, recursion is a common pattern.

1import java.util.ArrayList;
2import java.util.List;
3
4public class ComboDemo {
5    static void combinations(int[] arr, int k, int start, List<Integer> path) {
6        if (path.size() == k) {
7            System.out.println(path);
8            return;
9        }
10
11        for (int i = start; i < arr.length; i++) {
12            path.add(arr[i]);
13            combinations(arr, k, i + 1, path);
14            path.remove(path.size() - 1);
15        }
16    }
17
18    public static void main(String[] args) {
19        combinations(new int[]{1, 2, 3, 4}, 2, 0, new ArrayList<>());
20    }
21}

This gives predictable order and clear control over size k.

Handling Duplicate Values in Input

If input has duplicates and you need unique combination values, deduplicate first or skip repeated values during traversal.

Simple Python approach:

1from itertools import combinations
2
3items = [1, 1, 2, 2]
4unique = sorted(set(items))
5print(list(combinations(unique, 2)))

If index-level uniqueness matters, do not deduplicate values globally. Define uniqueness rule explicitly.

Streaming Versus Materialization

Materializing all combinations can exhaust memory fast.

# risky for large n
all_data = list(combinations(range(30), 15))

Prefer stream processing pipelines:

1total = 0
2for combo in combinations(range(30), 3):
3    total += 1
4print(total)

Streaming is often enough when you only aggregate or filter results.

If downstream logic only needs counts, maxima, or filtered subsets, streaming is almost always the better default because it keeps memory usage predictable.

Filtering During Generation

Apply pruning early when possible.

1from itertools import combinations
2
3items = [2, 4, 6, 8, 10]
4for c in combinations(items, 3):
5    if sum(c) <= 18:
6        print(c)

Filtering at generation time avoids storing large intermediate sets.

Choosing the Best Method

Use this rule of thumb:

• Python fixed-size combinations: itertools.combinations
• all sizes with streaming: generator over k
• languages without built-ins: recursive backtracking
• huge search spaces: constrain, sample, or prune

Best method is the one matching both correctness and resource limits.

Common Pitfalls

• Confusing combinations with permutations.
• Requesting all combinations without estimating output size.
• Materializing giant combination lists unnecessarily.
• Ignoring duplicate-value semantics in input.
• Using recursion without stack or depth considerations in large cases.

Summary

• Define combination requirements clearly before coding.
• Output-size growth is the main scalability constraint.
• Use built-in combinatorics tools where available.
• Prefer streaming and early filtering for larger datasets.
• Treat duplicate handling rules as part of core contract.