Can anyone explain me this piece of code?

public void generate(ArrayList a, ArrayList<ArrayList> output, ArrayList temp, int index)
{
for (int i = index; i < a.size(); i++)
{
temp.add(a.get(i));
output.add(new ArrayList(temp));
generate(a, output, temp, i+1);
temp.remove(temp.size() - 1);
}

Thumb rule of backtracking problem :

  1. choose an option
  2. explore it
  3. unchoose the last selected option
  4. explore
    repeat above cycle until we run out of options.

Let’s try to apply above logic in this problem :

Given set A= [1,2],temp <>,output<> let us start at index = 0

function(int[] A,ArrayList temp,ArrayList<ArrayList> output, int index)
{
if(index == A.length)
{
// no more elements to choose/ unchoose from the set , we have reached termination condition , add temp to output as it is one of the subset 
output.add(new ArrayList(temp);
}
else // if current index is valid index 
{ 
// we have two options ::
// include the current index element in our subset : 
temp.add(A[i]); // 1.choose
function(A,index+1,temp,output); //2. explore

// exclude the current index element ( by removing the last element added ) from our set 
temp.remove(temp.size()-1); //3. unchoose

function(A,index+1,temp,output); //4. explore
}

the output of above code is : ( kind of dfs ,goes till the end of an option until it can’t be explored further then add temp to the output , backtrack one step by unchoosing and continue )
[1, 2, 3]
[1, 2]
[1, 3]
[1]
[2, 3]
[2]
[3]
[]

This approach appears more intuitive to me

Now about the code you have posted , it has one bug :
the above function misses the empty subset case , ignoring that

Here what you are doing essentially is
1.start from an index & add it to the temp
2. add temp to the output
3. call the same function again with current_index +1,to extend the current temp
4. unchoose the current index (backtrack as we are done exploring all the possibilities with current temp and already added to output)

  public static void generate(int[] a, ArrayList<ArrayList<Integer>> output, ArrayList temp, int index)
{

for (int i = index; i < a.length; i++)
{
temp.add(a[i]);
output.add(new ArrayList(temp));
System.out.println("index = "+index + " choose  i= "+ i+" temp ="+ temp + " & add to output" );
generate(a, output, temp, i+1);
System.out.print("index = "+index +" unchoose i = "+ i+" from temp ="+temp);
temp.remove(temp.size() - 1);
System.out.print(" the new temp is" + temp);
System.out.println();
}
}

Output for above commented code :



index = 0 choose  i= 0 temp =[1]  & add to output
index = 1 choose  i= 1 temp =[1, 2]  & add to output
index = 2 choose  i= 2 temp =[1, 2, 3]  & add to output
index = 2 unchoose i = 2 from temp =[1, 2, 3] the new temp is[1, 2]
index = 1 unchoose i = 1 from temp =[1, 2] the new temp is[1]
index = 1 choose  i= 2 temp =[1, 3]  & add to output
index = 1 unchoose i = 2 from temp =[1, 3] the new temp is[1]
index = 0 unchoose i = 0 from temp =[1] the new temp is[]
index = 0 choose  i= 1 temp =[2]  & add to output
index = 2 choose  i= 2 temp =[2, 3]  & add to output
index = 2 unchoose i = 2 from temp =[2, 3] the new temp is[2]
index = 0 unchoose i = 1 from temp =[2] the new temp is[]
index = 0 choose  i= 2 temp =[3]  & add to output
index = 0 unchoose i = 2 from temp =[3] the new temp is[]


[1]  
[1, 2]  
[1, 2, 3]  
[1, 3]  
[2]  
[2, 3]  
[3]  

Hope your some doubts get clarified !

1 Like
Click here to start solving coding interview questions