Algorithm that generate all possible strings from N Tuples. Found Brute Force version, Recursive Version uses a Tree? I am trying to figure out a solution for a problem. Consider the following tuples (it could be any number of tuples, I am using four in this example): 


{A, B, C, D}
{E, F, G, H}
{I, J, K, L} 
{M, N, O, P}


Out of this tuples I have to construct a four-character string, but I can only choose one element from each tuple. Note that if I had \$N\$ tuples, it would be an \$N\$ character string.

The strings "AEIM", "BGLP", "DEIO" are valid examples. The string "EAIM" is not, because the A and E are in the wrong position.

I am able to brute force and get the solution, but there has to be a recursive way to do this... Because brute force does not solve for \$N\$ tuples

String[][] arr = { {"A", "B", "C", "D"}, {"E", "F", "G", "H"}, {"I", "J", "K", "L"}, {"M", "N", "O", "P"} };

String temp;
for(int i = 0; i &lt; 4; i++){

    for (int j = 0; j &lt; 4; j++){

        for (int k = 0; k &lt; 4; k++){

            for (int l = 0; l &lt; 4; l++){

                temp = arr[0][i] + arr[1][j] + arr[2][k] + arr[3][l];
                System.out.println(temp);

            }
        }
    }
}


I am aware that I could use a Tree to recursively solve this, however I do not know how to proceed... Any help is deeply appreciated!
The operation you're looking for is known as a Cartesian product on sets. An implementation of Cartesian product for Java Lists is somewhat as follows (all Lists have the same generic type T, otherwise we have to violate type safety, see below):

import java.util.Set;
import java.util.List;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.ArrayList;
import java.util.Arrays;

class CartesianProduct {
  // Set ensures that entries are unique
  private static &lt;T&gt; Set&lt;List&lt;T&gt;&gt; cartesianProduct2(Set&lt;List&lt;T&gt;&gt; accumulator, List&lt;T&gt; iterable) {
    // LinkedHashSet preserves insertion order, unlike HashSet
    Set&lt;List&lt;T&gt;&gt; product = new LinkedHashSet&lt;&gt;(); 
    for(List&lt;T&gt; elementAccumulator : accumulator) {
      for(T item : iterable) {
        // copy-on-write to ensure we don't change the arguments
        List&lt;T&gt; newElementAccumulator = new LinkedList&lt;&gt;(elementAccumulator);
        newElementAccumulator.add(item);
        product.add(newElementAccumulator);
      }
    }
    return product;
  }

  @SafeVarargs
  public static &lt;T&gt; Set&lt;List&lt;T&gt;&gt; cartesianProduct(List&lt;T&gt;... iterables) {
    // accumulator for fold
    Set&lt;List&lt;T&gt;&gt; product = new LinkedHashSet&lt;&gt;();
    // initialize accumulator to first iterable
    for(T item: iterables[0]) {
      // maintain the structure of the data
      List&lt;T&gt; elementAccumulator = new LinkedList&lt;&gt;();
      elementAccumulator.add(item);
      product.add(elementAccumulator);
    }
    // fold the rest of the iterables under the dyadic Cartesian product operation
    for(int i = 1; i &lt; iterables.length; ++i) {
      product = cartesianProduct2(product, iterables[i]);
    }
    return product;
  }

  public static void main(String[] args) {
    List&lt;String&gt; set1 = Arrays.asList(new String[]{"A", "B", "C", "D"}),
                set2 = Arrays.asList(new String[]{"E", "F", "G", "H"}),
                set3 = Arrays.asList(new String[]{"I", "J", "K", "L"}),
                set4 = Arrays.asList(new String[]{"M", "N", "O", "P"});

    List&lt;String&gt; output1 = new ArrayList&lt;&gt;();
    for(List&lt;String&gt; item : cartesianProduct(set1, set2, set3, set4)) {
      output1.add(String.join("", item));
    }

    String[][] arr = { {"A", "B", "C", "D"}, {"E", "F", "G", "H"}, {"I", "J", "K", "L"}, {"M", "N", "O", "P"} };

    List&lt;String&gt; output2 = new ArrayList&lt;&gt;();
    for(int i = 0; i &lt; 4; i++){
      for (int j = 0; j &lt; 4; j++){
        for (int k = 0; k &lt; 4; k++){
          for (int l = 0; l &lt; 4; l++){
               output2.add(arr[0][i] + arr[1][j] + arr[2][k] + arr[3][l]);
          }
        }
      }
    }
    System.out.println("Actual -&gt; Expected");
    for(int i = 0;i &lt; Math.min(output1.size(), output2.size()); ++i) {
      System.out.println(output1.get(i) + " -&gt; " + output2.get(i));
    }
    System.out.println(output1.size() == output2.size());
    System.out.println(output1.equals(output2));
  }
}


Unfortunately, this is more of a code dump, but this is the same thing itertools.product does in Python, and here's a more succinct Scala version of the core idea:

def cartesianProduct[S](vectors: Traversable[S]*): Traversable[Seq[_]] =
    cartesianProductMultiType(vectors)

  def cartesianProductMultiType(vectors: Traversable[Traversable[_]]): Traversable[Seq[_]] = {
    def cartesianProduct2[A, B](leftVector: IndexedSeq[IndexedSeq[A]], vector2: Traversable[B]): IndexedSeq[IndexedSeq[_]] =
      for {
        superSequence &lt;- leftVector
        element &lt;- vector2
      } yield superSequence :+ element

    vectors.foldLeft(IndexedSeq(IndexedSeq[Any]()))(cartesianProduct2(_, _)).distinct
  }


(This is in fact what I translated into Java, having coded this much earlier for a personal project).

This is not as memory-efficient as @coderodde's iterator version, but it is algorithmically simpler and easier to understand, I hope.

I put in a few tests in main so that you can check that this code does the same thing as yours.

Note that here you can replace the List&lt;T&gt; iterable and List&lt;T&gt;... iterables with Iterable&lt;T&gt; iterable and Iterable&lt;T&gt;... iterables to get an even more general version of the code which can find the Cartesian product of any collection of Iterables. Here, you should also swap

for(List&lt;T&gt; elementAccumulator : accumulator) {
      for(T item : iterable) {
          ...
      }
}


to

for(T item : iterable) {
      for(List&lt;T&gt; elementAccumulator : accumulator) {
          ...
      }
}


to ensure that you don't consume the iterator of iterable multiple times - creating the iterator might be expensive or slow, say reading from a file. This'll make the output come out in a different order from what you give us - it'll be a post-order traversal instead of a pre-order one (see below).

Since @coderodde has already addressed the main point of iterators and memory-efficiency, this is more educational as you were asking for a recursive solution. Although this particular solution is not recursive, it does utilize the concept of divide-and-conquer with a base case, so it should be helpful to you.

About trees: see if you can recognize the tree structure in this program.

Hint: it is a balanced \$n\$-level tree where \$n\$ is the number of tuples, with each node having \$\left|T_i\right|\$ children, where \$\left|T_i\right|\$ denotes the number of elements in tuple \$T_i\$. In fact, the \$i^\text{th}\$ level is just the elements of \$T_i\$ repeated as the children of every node of level \$i-1\$. The output of this program is a depth-first search with pre-order traversal of this tree, splitting the output into words at each backtrack (recursion unwind). The output at any given point during the execution is the path traversed in the tree till that point.

An exercise - try writing a program which explicitly makes this tree and prints every path from each root to each leaf, splitting the output into words at each backtrack.

Here's an example tree for the set of tuples {('A','B'), ('C', 'D'), ('E', 'F'})} (note how each required word is the pre-order path from the empty root to a leaf):



Also, take a look at these data structures - Trie and Suffix Tree.