Cracking the Coding Interview: Why does the recursive subset algorithm increase the index rather than decreasing it?

Question

In chapter 8 of Cracking the Coding Interview, 6th Edition, there's a question for finding all the subsets, and this is the given solution:

Arraylist<Arraylist<Integer>> getSubsets(Arraylist<Integer> set, int index) {
    Arraylist<Arraylist<Integer>> allsubsets;
    if (set.size()== index) {//Base case - add empty set
        allsubsets = new Arraylist<Arraylist<Integer>>(); 
        allsubsets.add(new Arraylist<Integer>()); // Empty set
    } else {
        allsubsets = getSubsets(set, index+ 1);
        int item = set.get(index);

        Arraylist<Arraylist<Integer>> moresubsets = new Arraylist<Arraylist<Integer>>();

        for (Arraylist<Integer> subset : allsubsets) {
            Arraylist<Integer> newsubset = new Arraylist<Integer>();
            newsubset.addAll(subset);
            newsubset.add(item);
            moresubsets.add(newsubset);
        }
        allsubsets.addAll(moresubsets);
    }
    return allsubsets;
}

To my understanding, I need to add the current element to all the subsets found for the previous element from the given set. I don't understand why the recursive call takes index+1 as a given parameter instead of index-1. Is this a typo or is my understanding incorrect?

Answer 1

The idea behind this particular recursive function seems to be that getSubsets(set, i) means "generate and return all subsets of the elements in the input list s from index i and forward." If you look at how the recursion works, it does so as follows:

• If i == set.size(), then we're supposed to generate all subsets of the elements from index set.size() and forward. There aren't any elements here, so the only subset is the empty set.
• Otherwise, notice that each subset of the elements of set, starting at index i, either include the ith element or they don't. The subsets that don't contain the ith element are precisely the subsets of set starting from position i + 1 and forward. The ones that do are formed by taking those subsets, then adding in the ith element to them.

So in that sense, the reason the recursion goes to index i + 1 rather than i - 1 is because the intuition is to look at subsets of elements starting from position i and going to the end.

You could alternatively write this function to list subsets from index 0 up through index i if you'd like and then step i downward toward 0. It's a perfectly reasonable way to do this and a great exercise to code it up yourself!