CODEWITHSUNDEEP
java
user1896796
user1896796

Reputation: 749

Understanding flow of recursion in calculating powersets

I have found a code which is calculating powersets of an array .

I am not able to understand what is happening inside the subseq() method. As per my understanding and what I could see while debugging - 

1. first [] is added.
2. Goes inside loop , `i=0` adds `[1]`
3. recursive call , `i=1` adds `[1,2]`
4. recursive call , `i=2` adds `[1,2,3]`

When i =3, it should not go inside the loop itself, How come after this, the execution is going to remove. Could you help me understand this.

public class printSubSequences {

    public static void main(String[] args) {
        int[] num = {1,2,3};
        List<List<Integer>> subsets = new ArrayList<>();
        subseq(0, num, new ArrayList<Integer>(), subsets );

        System.out.println(subsets);

    }

    public static void subseq(int index, int[] num, List<Integer> current, List<List<Integer>> subsets) {

        subsets.add(new ArrayList<>(current));
        for(int i = index ; i< num.length; i++) {
            current.add(num[i]);
            subseq(i+1, num, current, subsets);
            current.remove(current.size() -1);
        }

    }

}

Upvotes: 0

Views: 75

Answers (2)

Oleksandr Pyrohov
Oleksandr Pyrohov

Reputation: 16226

It's a simple backtracking algorithm.

When recursion hits the bottom:

subseq(0, {1,2,3}, [], []);
    subseq(1, {1,2,3}, [1], [[]]);
        subseq(2, {1,2,3}, [1,2], [[], [1]]);
            subseq(3, {1,2,3}, [1,2,3], [[], [1], [1,2]]); <---

the for loop is skipped in this frame, because i == num.length; so, the code returns to the previous frame, where i was 2, and the line immediately after the subseq(...) is being executed:

current.remove(current.size() -1);

At this point current = [1,2,3], so the last element 3 will be removed.

Upvotes: 1

Saurabh
Saurabh

Reputation: 943

Simple funda of Java is, it will execute each and every line one after another. It will store method call in thread's stack memory.

For your example,

  1. first [] is added.
  2. Goes inside a loop, i=0 adds [1]
  3. recursive call

It will call subseq() and adds the call in thread's stack, but please note current.remove(current.size() -1) is still pending. For our understanding give this call alias A , i=1 adds [1,2], thread stack [A]

  1. recursive call

same way as exalian above it will call subseq() again and adds it in method stack. Lets give this call alias B, i=2 adds [1,2,3], thread stack [B,A]

  1. Jump back to the previous call

Now, for the third-time condition will going to fail. So it will skip the loop. Now, the pointer will go back to the previous calls which are pending. So, it will look into the stack [B,A] and go to the call B. It will start executing operations which are thereafter the recursion method call and then it will remove that from the stack. For us after performing remove operation stack would be like [A] removes 3

  1. Jump back to the previous call

The same way it will do for operation A and removes 2

  1. Jump back to the original call

It will remove 1

Please note, the operation alias that I have mentions its totally for our understaing of concept. They are actually named as a method name. You can learn more about recursion on this.

Upvotes: 0

Related Questions