1 year ago

#351000

test-img

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

Accepted video resources