Create a set of lists from two lists via recursion

I have looked through a lot of questions on this site with some similar basic concepts, however after many hours of trying to solve this problem on my own and I still lose the overview. If there is another question that answers this, I'll be more than happy to take a look at it.

Ultimately I want to create a recursive method such that it takes two lists and returns a List of strings :

//Example of such a function definition
private static Set<List<String>> myRecursiveMethod(List<String> listOne, 
List<String> listTwo) {
}

      

        
        
        
      

    

When I say "Set of string lists" I mean specifically the following: (Note: "AD" == "DA")

// if the two following lists are INPUTTED into myRecursiveMethod();
// listOne = ["A","B"]
// listTwo = ["C","D"]
// the following set is OUTPUTTED: [["AC","BD"],["AD","BC"]] 

      

        
        
        
      

    

Thus, if listOne and listTw had three elements, the set would have SIX elements. i.e:

// listOne = ["A","B","C"]
// listTwo = ["D","E","F"]
// OUTPUTTED: [["AD","BE","CF"],["AD","BF","CE"],["BD","AE","CF"],
// ["BD","AF","CE"],["CD","AE","BF"],["CD","AF","BE"]] 

      

        
        
        
      

    

I tried to write this using a double extended FOR loop so I can understand the logic. My FOR loop is terrible and only works for the HARD-CODED constraint for list.size () == 2.

// Create Lists and append elements 
List<String> listOne = new ArrayList<String>();
listOne.add("A");
listOne.add("B");

List<String> listTwo = new ArrayList<String>();
listTwo.add("C");
listTwo.add("D");

// List One = ["A","B"]
// List Two = ["C","D"]

// Create new List
List<List<String>> newList = new ArrayList<List<String>>();
Integer counter = 0;

    for (String s : listOne) {
        counter++;
        for (String p : listTwo) {

            // A HARD-CODED bad implementation of this method
            if (counter < 3) {
                List<String> newListTwo = new ArrayList<String>();
                newListTwo.add(s.concat(p));
                newList.add(newListTwo);

            } else if (!(counter % 2 == 0)) {
                newList.get(1).add(s.concat(p));

            } else {
                newList.get(0).add(s.concat(p));
            }
        }
    }
    System.out.println(newList); // = [["AC","BD"],["AD","BC"]] 

      

        
        
        
      

    

Also you may notice that I have defined List <List <String → Instead of Set <List <String →. It was due to my failed coding attempt which relies on the list.get () method.

So my current recursive method looks like this:

private static Set<List<String>> myRecursiveMethod(List<String> listOne, 
List<String> listTwo) 
{
    //Base Case:
    if (listOne.isEmpty){
        return new HashSet<List<String>>;
    }
    //Recursive Case:
    else {
        String listOneFirst = listOne.get(0);
        String listTwoFirst = listTwo.get(0);

        List<String> sampleList = new ArrayList<String>();
        sampleList.add(listOneFirst+listTwoFirst);

        Set<List<String>> newSet = new HashSet<List<String>>(myRecursiveMethod())
        newSet.add(sampleList);
        return newSet;
    }
}

      

        
        
        
      

    

This method only works like this:

INPUT:

• List One = ["A", "B"]
• List two = ["C", "D"]

OUTPUT:

• [["AC"] ["BD"]]

DESIRED OUTPUT:

• [["AC", "BD"], ["AD", "BC"]]

EDIT:

After looking at the answers, my WIP code for the class:

private static Set<List<String>> myRecursiveMethod(List<String> listOne,
        List<String> listTwo) {

    //Backup Case (user enters an empty list)
    if (listOne.isEmpty()){
        return new HashSet<List<String>>();
    }

    // Base Case:
    if (listOne.size() == 1) {
        List<String> mergedStrings = new ArrayList<>();
        for (String s : listTwo) {
            mergedStrings.add(listOne.get(0).concat(s));
        }
        Set<List<String>> builtHashSet = new HashSet<List<String>();
        builtHashSet.add(mergedStrings);
        return builtHashSet;
    }
    // Recursive Case:
    else {

        // Ensure original list values arn't changed.
        List<String> newListOne = new ArrayList<String>(listOne);
        List<String> newListTwo = new ArrayList<String>(listTwo);

        //first two elements...I don't think this is correct
        String listOneFirst = newListOne.get(0);
        String listTwoFirst = newListTwo.get(0);
        List<String> sampleList = new ArrayList<String>();
        sampleList.add(listOneFirst + listTwoFirst);

        //used for making recursive case smaller
        newListOne.remove(0);

        // Calls recursion
        Set<List<String>> newSet = new HashSet<List<String>>(
                myRecursiveMethod(newListOne, newListTwo));
        newSet.add(sampleList);

        return newSet;
    }
}