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

Answer 1

(I don't know how I ended up being here, this tab really might have been open for 2 years)

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

With loops it's trivial, you need a loop-pair for start and end indices:

const list = ["Janet", "Robert", "Morgan", "Char"];
for (var start = 0; start < list.length; start++)
  for (var end = start + 1; end < list.length + 1; end++) // end is exclusive
    console.log(list.slice(start, end).join()); // so, this is like list.subList(start,end)

Then it can be rewritten into a single loop, and make it a while, managing the indices manually:

const list = ["Janet", "Robert", "Morgan", "Char"];
var start = 0;
var end = 1;
while (start < list.length) {
  console.log(list.slice(start, end).join());
  end++;
  if (end > list.length) {
    start++;
    end = start + 1;
  }
}

Then a single loop is easy to write as "recursion":

function sublists(list, start, end) {
  console.log(list.slice(start, end).join());
  end++;
  if (end > list.length) {
    start++;
    end = start + 1;
  }
  if (start < list.length)
    sublists(list, start, end);
}

sublists(["Janet", "Robert", "Morgan", "Char"], 0, 1);

So, technically we are recursive now, though we don't really benefit from it.

---

Then we can start going backwards, keeping the two loops separately, and making an outer-inner recursion pair of them. Coincidentally the inner one (`subsublists()` here) can be very similar to your original attempt (without the exception of course):

function subsublists(list) {
  console.log(list.join());
  if (list.length > 1)
    subsublists(list.slice(0, list.length - 1));
}

function sublists(list) {
  subsublists(list);
  if (list.length > 1)
    sublists(list.slice(1));
}

sublists(["Janet", "Robert", "Morgan", "Char"], 0);

Or, in Java:

public static void main (String[] args) {
    ArrayList<String> list = new ArrayList<>(List.of("Janet", "Robert", "Morgan", "Char"));
    sublists(list);
}
public static void subsublists(List<String> list) {
    System.out.println(list);
    if(list.size()>1)
        subsublists(list.subList(0,list.size()-1));
}
public static void sublists(List<String> list) {
    subsublists(list);
    if(list.size()>1)
        sublists(list.subList(1,list.size()));
}

Live version: https://ideone.com/JU44Jj

Output:

[Janet, Robert, Morgan, Char]
[Janet, Robert, Morgan]
[Janet, Robert]
[Janet]
[Robert, Morgan, Char]
[Robert, Morgan]
[Robert]
[Morgan, Char]
[Morgan]
[Char]

Answer 2

If we want to permutate all the value in the list then we can use this code->

 public static void main(String[] args) {
        List<String> list = Arrays.asList("Janet", "Robert", "Morgan", "Char");
        recursiveprint(list,  new boolean[list.size()], "");

    }

    private static void recursiveprint(List<String> list,  boolean b[], String s) {

        System.out.println(s);
        for (int j = 0; j < list.size(); j++) {
            if (b[j] == false) {
                b[j] = true;
                recursiveprint(list,  b, s + list.get(j)+"  ");

                b[j] = false;
            }
        }
    }

Answer 3

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.