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.
与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…