1 year ago
#351000
eswcs
Struggling to understand recursive backtracking in Java
I am not understanding how recursive backtracking works. We did this example in class, but I don't understand why it backtracks when it is always adding 1 to level or i. Why don't we have to subtract at some point to actually go back through the array? Also, why do 2 recursive calls work, and not produce some kind of error?
public class Subsets {
public static void main(String[] args) {
int[] arr = {3,7,12};
printSubsets(arr);
}
public static void printSubsets(int[] a) {
boolean[] inSet = new boolean[a.length];
printSubsets(a, inSet, 0);
}
public static void printSubsets(int[] a, boolean[] inSet, int level) {
if(level == a.length) {
System.out.print("{");
int i = 0;
while(i < inSet.length && !inSet[i]) {
i++;
}
if(i < inSet.length) {
System.out.print(a[i]);
i++;
for(; i < inSet.length; i++) {
if(inSet[i])
System.out.print(", " + a[i]);
}
}
System.out.print("}");
System.out.println();
}
else {
//System.out.println(level + " " + inSet[level] + " ");
inSet[level] = false;
printSubsets(a, inSet, level+1);
inSet[level] = true;
printSubsets(a, inSet, level+1);
}
}
}
java
arrays
recursion
backtracking
0 Answers
Your Answer