These problems address the last general situation where recursion is commonly useful (which did not make it into the regular part of the course): Problems where you recursively find ALL possible solutions, not just one. This pattern may be easier to figure out if you look at one or two full solutions, and then try to write the rest.
If you do the whole problems here, they are harder than in your assignments and exams, because I do not start off giving you the recursive helping method documentation that sets things up. (In exams I will use tree situations or other places with recursive definitions, so the recursive pattern should be fairly clear.)
These problems become a lot easier if you read part way into my solution. There is a fuller explanation under How to reduce the problems to simpler ones.
// Print all subsets of e, one per line,
// assuming all elements of e are distinct.
public static void subsets(char[] e) {
// Print all subsets of e with n elements, one subset per line,
// assuming all elements of e are distinct,
and 0 <= n <= e.length.
// (This can be derived from previous code, assembling all subsets,
// but try to do it more directly.)
public static void subsetsN(char[] e, int n) {
// Print out the elements of e in all possible orders,
// assuming all elements of e are distinct.
public static void permute(char[] e) {
// Return a count of all the sums of subsets of one or more elements
from x
// that add to sum. Order does not matter.
// For simplicity you may assume that all the elements of x
are distinct.
// Again this could be done by finding all subsets, but do it
more directly.
public static int countSums(int[] x, int sum) {
// code
}
// complete main program
public static void main(String[] args) { // illustration
of methods above.
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 permutatons: ");
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 permutations: ");
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");
} // end of main
} // end of ListRecursion
- - - - - - - - - - - - - - - - -
set: abc
All subsets:
abc
ab
ac
a
bc
b
c
// empty set
All subsets with 2 elements:
ab
ac
bc
All permutatons:
abc
acb
bac
bca
cba
cab
- - - - - - - - - - - - - - - - -
set: abcd
All subsets:
abcd
abc
abd
ab
acd
ac
ad
a
bcd
bc
bd
b
cd
c
d
// empty set
All subsets with 1 element:
a
b
c
d
All subsets with 2 element:
ab
ac
ad
bc
bd
cd
All permutatons:
abcd
abdc
acbd
acdb
adcb
adbc
bacd
badc
bcad
bcda
bdca
bdac
cbad
cbda
cabd
cadb
cdab
cdba
dbca
dbac
dcba
dcab
dacb
dabc
- - - - - - - - - - - - - - - - -
Consider numbers: 2 3 5
2 sums adding to 5 // 2+3, 5
0 sums adding to 4
- - - - - - - - - - - - - - - - -
Consider numbers: 1 2 3 4 5 6
4 sums adding to 6 // 6, 1+5, 2+4, 1+2+3
All of my recursive methods have under 10 lines of code, but they may be tough to imagine. If you look at one solution, it might give you some idea how to go about another problem, though the manners in which the recursive calls aid in the larger situation does vary with the context.
Right after the heading for each method, I have a comment indicating in general how to break the problem into steps. (All these problems are pretty similar at this level.)
Then after a blank line I have a single line calling my recursive helping method, showing the initial parameters.
Next is the heading of the recursive helping method, possibly adding some meaningful parameter names.
Next is documentation on the helping method -- at this point you are in about the same place as I left you for Queens and the expression evaluation -- seeing the helping method headings and documentation.
Finally there is concise code for the recursive helping method solution.
Then I go on to the next (nonrecursive) method from the skeleton.
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");
} // end of main
// - - - - - start of method solutions - - - - - - - - -
// Print all subsets of e, one per line,
// assuming all elements of e are distinct.
public static void subsets(char[] e) {
// Implement as multistep process: include
or do not include next char.
subsetsRest(e, new boolean[e.length], 0);
}
private static void subsetsRest(char[] e, boolean[] isIn,
int iStart) {
/*
e is the array of possible characters.
e[j] is in the set if isIn[j] is true, for each
j < iStart.
isIn[j] is false for each j >= iStart.
isIn ends in the same state it starts the method.
The method provides all choices of true and false
values for every
index >= iStart, and prints the result if iStart
== e.length.
*/
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);
// do include e[iStart]
isIn[iStart] = false; // placing isIn
back in its original state
subsetsRest(e, isIn, iStart+1);
// not include e[iStart]
}
}
// Print all subsets of e with n elements, one subset per line,
// assuming all elements of e are distinct,
and 0 <= n <= e.length.
// (This can be derived from previous code, assembling all subsets,
// but try to do it more directly.)
public static void subsetsN(char[] e, int n) {
// Implement as multistep process: include
or do not include next char.
subsetsNRest(e, new char[n], 0, 0);
}
private static void subsetsNRest(char[] e, char[] sub, int eStart,
int subStart) {
/*
e is the array of possible characters.
If eStart == e.length, and subStart < sub.length,
return doing nothing.
If subStart == sub.length, print sub.
Letters sub[j] are chosen already if j < subStart.
Fill remaining places in sub with some elements
e[k], k >= eStart.
Returns with sub[j] unchanged if j < eStart.
*/
if (subStart == sub.length)
System.out.println(sub);
else if (eStart < e.length) {
sub[subStart] = e[eStart];
subsetsNRest(e, sub, eStart+1, subStart+1);
// do add e[eStart]
subsetsNRest(e, sub, eStart+1, subStart);
// do not add e[eStart]
}
}
// Print out the elements of e in all possible orders,
// assuming all elements of e are distinct.
public static void permute(char[] e) {
// implement as multistep process:
// choose element at index i from elements
now at index >= i
permuteRest(e, 0);
}
private static void permuteRest(char[] e, int iStart) {
/*
e is a possible permutation.
Keep e[j] in its position if j < iStart.
Do all permutations for elements e[j], j >= iStart.
Return with the order of e elements the same as
the beginning.
*/
if (iStart == e.length)
System.out.println(e);
else
for (int j = iStart; j < e.length;
j++) {
swap(e, iStart, j); // helping
method next
permuteRest(e, iStart+1);
swap(e, iStart, j); // return
to original state
}
}
private static void swap(char[] e, int i, int j) {
char temp = e[i];
e[i] = e[j];
e[j] = temp;
}
// Return a count of all the sums of subsets of one or more elements
from x
// that add to sum. Order does not matter.
// For simplicity you may assume that all the elements of x
are distinct.
// Again this could be done by assembling all subsets, but do
it more directly.
public static int countSums(int[] x, int sum) {
// Implement as multistep process: include
next number or not in sum.
return countSumsRest(x, sum, 0);
}
private static int countSumsRest(int[] x, int sumMissing, int
iStart) {
/*
x is the array of numbers you can add.
sumMissing is the desired sum from some of the element
x[j], j >= iStart.
*/
if (iStart == x.length) return 0;
int count = 0;
count += countSumsRest(x, sumMissing, iStart+1);//
sums not using x[iStart]
sumMissing -= x[iStart];
// do use x[iStart]
if (sumMissing == 0) count++;
// sum ending here?
count += countSumsRest(x, sumMissing, iStart+1);//
longer sums using x[iStart]
return count;
}
} // end of ListRecursion