Recursive problem without using any sort of loop NO forwhile

Recursive problem without using any sort of loop (NO for/while loop)

Write a method subsets that uses recursive backtracking to find every possible sub-list of a given list. A sub-list of a list L contains 0 or more of L\'s elements. Your method should accept a List of strings as its parameter and print every sub-list that could be created from elements of that list, one per line. For example, suppose a variable called list stores the following elements: [Janet, Robert, Morgan, Char] The call of subsets (list); would produce output such as the following: [Janet, Robert, Morgan, [Janet, Robert, Morgan] [Janet, Robert, Char] [Janet, Robert] [Janet, Morgan, Char] [Janet, Morgan] [Janet, Char] [Janet] [Robert, Morgan, Char] [Robert, Morgan] [Robert, Char] [Robert] [Morgan, Char] [Morgan] [Char] [] The order in which you show the sub-lists does not matter, and the order of the elements of each sub-list also does not matter. The key thing is that your method should produce the correct overall set of sub-lists as its output. Notice that the empty list is considered one of these sub-lists. You may assume that the list passed to your method is not null and that the list contains no duplicates. Do not use any loops in solving this problem. It can be hard to see a pattern from looking at the lines of output. But notice that the first 8 of 16 total lines of output constitute all the sets that include Janet, and the last 8 lines are the sets that do not have her as a member. Within either of those groups of 8 lines, the first 4 of them are all the sets that include Robert, and the last 4 lines are the ones that do not include him. Within a clump of 4, the first 2 are the ones including Morgan, and the last 2 are the ones that do not include Morgan. And so on. Once again, you do not have to match this exact order, but looking at it can help with figuring out the patterns and the recursion.

Solution

program

     public class ListRecursion
{
public static void main(String[] args)
{
char[] c3 = {\'a\', \'b\', \'c\'};
char[] c4 = {\'a\', \'b\', \'c\', \'d\'};
int[] i3 = {2, 3, 5};
int[] i6 = {1, 2, 3, 4, 5, 6};
System.out.println(\"- - - - - - - - - - - - - - - - -\");
System.out.print(\"set: \");
System.out.println(c3);
System.out.println(\"All subsets: \");
subsets(c3);
System.out.println(\"All subsets with 2 elements: \");
subsetsN(c3, 2);
System.out.println(\"All permutations: \");
permute(c3);
System.out.println(\"- - - - - - - - - - - - - - - - -\");
System.out.print(\"set: \");
System.out.println(c4);
System.out.println(\"All subsets: \");
subsets(c4);
System.out.println(\"All subsets with 1 element: \");
subsetsN(c4, 1);
System.out.println(\"All subsets with 2 element: \");
subsetsN(c4, 2);
System.out.println(\"All permutatons: \");
permute(c4);
System.out.println(\"- - - - - - - - - - - - - - - - -\");
System.out.print(\"Consider numbers: \");
for (int j = 0; j < i3.length; j++)
System.out.print(\" \" + i3[j]);
System.out.println();
System.out.println(countSums(i3, 5) + \" sums adding to 5\");
System.out.println(countSums(i3, 4) + \" sums adding to 4\");
System.out.println(\"- - - - - - - - - - - - - - - - -\");
System.out.print(\"Consider numbers: \");
for (int j = 0; j < i6.length; j++)
System.out.print(\" \" + i6[j]);
System.out.println();
System.out.println(countSums(i6, 6) + \" sums adding to 6\");
}
public static void subsets(char[] e)
{
subsetsRest(e, new boolean[e.length], 0);
}
private static void subsetsRest(char[] e, boolean[] isIn, int iStart)
{
if (iStart == e.length) {
for (int j = 0; j < e.length; j++)
if(isIn[j]) System.out.print(e[j]);
System.out.println();
}
else
{
isIn[iStart] = true;
subsetsRest(e, isIn, iStart+1);   
isIn[iStart] = false;
subsetsRest(e, isIn, iStart+1);   
}
}
public static void subsetsN(char[] e, int n)
{
subsetsNRest(e, new char[n], 0, 0);
}
private static void subsetsNRest(char[] e, char[] sub, int eStart, int subStart)
{
if (subStart == sub.length)
System.out.println(sub);
else if (eStart < e.length)
{
sub[subStart] = e[eStart];
subsetsNRest(e, sub, eStart+1, subStart+1);
subsetsNRest(e, sub, eStart+1, subStart);
}
}
public static void permute(char[] e)
{
permuteRest(e, 0);
}
private static void permuteRest(char[] e, int iStart)
{
if (iStart == e.length)
System.out.println(e);
else
for (int j = iStart; j < e.length; j++)
{
swap(e, iStart, j);
permuteRest(e, iStart+1);
swap(e, iStart, j);
}
}
private static void swap(char[] e, int i, int j)
{
char temp = e[i];
e[i] = e[j];
e[j] = temp;
}
public static int countSums(int[] x, int sum)
{
return countSumsRest(x, sum, 0);
}
private static int countSumsRest(int[] x, int sumMissing, int iStart)
{
if (iStart == x.length) return 0;
int count = 0;
count += countSumsRest(x, sumMissing, iStart+1);
sumMissing -= x[iStart];
if (sumMissing == 0) count++;   
count += countSumsRest(x, sumMissing, iStart+1);
return count;
}
}