Introduction

Problems described as "all combinations of a list n levels deep" usually mean one of two things: combinations from a single list, or the Cartesian product across multiple levels of choices. In Java, the most common recursive solution for the multi-level case is backtracking: build one partial result, recurse to the next level, and remove the last choice when you return.

Clarify the Problem Shape First

Suppose you have a list of lists like this:

• level 1: A, B
• level 2: 1, 2
• level 3: X, Y

The desired output is often:

• 'A, 1, X'
• 'A, 1, Y'
• 'A, 2, X'
• 'A, 2, Y'
• 'B, 1, X'
• 'B, 1, Y'
• 'B, 2, X'
• 'B, 2, Y'

That is not the same as choosing unordered subsets from one flat list. It is a depth-by-depth product of choices.

Recursive Backtracking Fits Naturally

Backtracking works well because the structure is recursive by definition:

• choose one item at the current depth
• recurse to the next depth
• when you return, remove that item and try the next choice

A Java implementation looks like this:

1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.List;
4
5public class CartesianProduct {
6    public static List<List<String>> generate(List<List<String>> levels) {
7        List<List<String>> result = new ArrayList<>();
8        backtrack(levels, 0, new ArrayList<>(), result);
9        return result;
10    }
11
12    private static void backtrack(
13            List<List<String>> levels,
14            int depth,
15            List<String> current,
16            List<List<String>> result) {
17
18        if (depth == levels.size()) {
19            result.add(new ArrayList<>(current));
20            return;
21        }
22
23        for (String value : levels.get(depth)) {
24            current.add(value);
25            backtrack(levels, depth + 1, current, result);
26            current.remove(current.size() - 1);
27        }
28    }
29
30    public static void main(String[] args) {
31        List<List<String>> levels = Arrays.asList(
32            Arrays.asList("A", "B"),
33            Arrays.asList("1", "2"),
34            Arrays.asList("X", "Y")
35        );
36
37        List<List<String>> combinations = generate(levels);
38        for (List<String> combination : combinations) {
39            System.out.println(combination);
40        }
41    }
42}

This produces every valid path through the levels.

Why Backtracking Works

The algorithm explores a tree of choices. At each depth, it tries every value available at that level. The current list holds the partial path so far.

The important detail is this line:

result.add(new ArrayList<>(current));

You must copy the current path before storing it. Otherwise, later backtracking steps would mutate the same list object and corrupt every saved result.

Iterative Alternatives

You can also build the product iteratively. Start with one empty combination, then expand it level by level.

Conceptually:

1. start with [[]]
2. for each new level, append each option to each existing partial combination
3. replace the partial list with the newly expanded one

This can be elegant for some workloads, but the recursive version is often easier to understand and adapt.

Complexity

If each level has m choices and there are n levels, the total number of outputs is roughly m^n. That means the algorithm must do exponential work because the output itself is exponential.

This is an important point: no clever implementation can avoid that if you truly need every combination. The best you can do is generate them efficiently and avoid unnecessary overhead.

If You Really Meant Simple Combinations

Sometimes the phrase "combinations" refers to choosing k items from one list rather than building one choice per level. That is a different problem and needs a different backtracking rule.

So before optimizing, make sure everyone agrees on whether the target is:

• Cartesian product across levels
• or k-element combinations from one collection

Many implementation errors come from solving the wrong combinatorics problem.

Common Pitfalls

The biggest mistake is forgetting to copy the current path before adding it to the results. That causes every stored result to end up identical.

Another mistake is mixing up Cartesian products and unordered combinations. They sound similar in English but are not the same algorithm.

People also underestimate output size. If each level has many choices, the number of results grows very quickly.

Finally, watch for empty levels. If one level has no choices, the full product is empty, and your method should handle that case deliberately.

Summary

• Multi-level "combinations" in Java are often really a Cartesian product problem.
• Recursive backtracking is a clean way to generate every path through the levels.
• Copy the current partial result before storing it.
• The output size is inherently exponential in the number of levels.
• Make sure the problem is not actually asking for simple k-element combinations instead.