java - Printing every possible sub-list of a list using recursion

Question

I am having trouble solving this recursion problem. Recursion is quite difficult to understand and be able to code as I am new to coding. The problem is to write a recursive method to find every possible sub-list of a given list. Your method should accept a list of strings as a parameter and print every sub-list that could be created from elements of that list, one per line. Assume there is no duplicates and the list is not null. Do not use any loops.

The only possible way I can think of doing this is with a for loop or use more parameters but I can't per instructions. This is what I have so far. I checked the list api it says there is a subList method you can use. I was able to print the first 5 possible sublists just by substracting -1 from the list size every recursion and then I get an index error. This is very frustrating so if anyone has any tips or pointers that would greatly be appreciated.

If you can possibly solve it with loops, I'd love to see how you would solve it.

public static void main(String[]args){
        ArrayList<String> list = new ArrayList<>(List.of("Janet", "Robert", "Morgan", "Char"));
        subsets(list);
        
    }


public static void subsets(List<String> list) {
        int n = list.size();
        if(list.isEmpty()){
            System.out.println(list);

        }
        if(n > 0){
            System.out.println(list.subList(0 , n));
        }
        subsets(list.subList(0,n -1));
    }

Results of my code

question from:https://stackoverflow.com/questions/65907305/printing-every-possible-sub-list-of-a-list-using-recursion

Answer 1

The best solution I came up with is based on randomness, I'll post in even though it is not what is expected by the Java Programming textbook.

You can calculate how many distinct k-combinations of K elements exists in a list of N elements. For example:

• One combination of 4 elements exists in a list of 4
• 4 combinations of 3 elements exist in a list of 4.

The idea is to have as args of the recursive method:

• The initial list you want to extract sublists
• A list of every sublist already printed
• The number K of elements of the wanted sublist size

You should then have the following method signature:

public static void subsets(List<String> list, ArrayList<List<String>> alreadyPrinted, int nbOfElementsInTheSubList);

and the call in your main method will be

subsets(list, new ArrayList<>(), list.size());

Now in the body of the recursive method, process as follow (pseudo-code)

• Pick a sublist of nbOfElementsInTheSubList random elements from list that is not in alreadyPrinted, print it, and add it to alreadyPrinted
• compute combinationNumber = list.size() choose nbOfElementsInTheSubList (ie: the number of nbOfElementsInTheSubList-combination in list)
• compare it to alreadyThere, the number of combination of nbOfElementsInTheSubList elements presents in alreadyPrinted
  • if alreadyThere = combinationNumber : You have all the nbOfElementsInTheSubList-Combination available in list, you can call recursively your method using (nbOfElementsInTheSubList - 1) as the last arg
  • else : You are missing at least one of the nbOfElementsInTheSubList-Combination available in list. Call subset again using the same nbOfElementsInTheSubList but with the updated alreadyPrinted

I doubt this is an optimal solution, so I bookmarked your topic since I am sincerely curious about the expected code.