can anybody explains the code and also recursion tree

Question

i' am unable to make recursion tree i saw many videos on this question but nobody is telling that after first left most leaf node completion how the full recursion is made cause after there will two variable which index and j are updated. According to me if index is initialized in j then all elements are swapped by themselves.

how the code works please explain me

Example 1:

Input: nums = [1,2,3] Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

class Solution {
    private:
    void solve(vector <int>nums, vector<vector<int>> &ans, int index){
        if(index >= nums.size()){
            ans.push_back(nums);
            return;
        }
    for(int j= index; j<nums.size(); j++){
        swap(nums[index] , nums[j]);
        solve(nums, ans, index+1);
        //backtrack

        swap(nums[index], nums[j]);
    }

    }
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;
        int index=0;
        solve(nums, ans, index);
        return ans;
    }
};

Answer 1

all elements are swapped by themselves.

Yes, the very first permutation that is generated is the original order of nums. This should be included, as that is one of the valid permutations.

Take a look at this loop:

    for(int j= index; j<nums.size(); j++){
        swap(nums[index] , nums[j]);
        solve(nums, ans, index+1);
        //backtrack
        swap(nums[index], nums[j]);
    }

The idea behind this loop is to have all values (from index to the end) take turns in taking the position at index, and then generate all permutations of the "rest" of the array (from index+1 onwards).

The first iteration of the loop will choose nums[index] to take that position, so it actually doesn't have to move. So yes, the swap is doing nothing then. That's OK. But after the recursive call has returned, and the second swap is executed (which again does not move anything), we get to the next iteration of this loop:

Now j is index+1, and so the swap has an effect. It places the selected value (at index j) at index index, and now again a recursive call is made to generate all the permutations of the "rest" of the array.

Visualising

So for the example nums = [1,2,3], we can represent what happens in a table, where the different recursion levels are each represented as a separate column. The value of index actually corresponds to the recursion depth (starting with 0), so I'll put that in the column headers. The last column is reserved to show the current state of nums. It is only filled in when something important happens, like a swap or pushing that result in the ans vector.

I'll abbreviate some of the quoted code, so that swap(0, 2) is short for swap(nums[0],nums[1]), and push_back short for ans.push_back(nums), and solve() short for solve(nums, ans, index+1)...

index==0	index==1	index==2	index==3	nums
j=0				[1,2,3]
swap(0,0)
solve()
	j=1
	swap(1,1)
	solve()
		j=2
		swap(2,2)
		solve()
			j=3
			push_back	[1,2,3] *
		swap(2,2)
		j=3
	swap(1,1)
	j=2
	swap(1,2)			[1,3,2]
	solve()
		j=2
		swap(2,2)
		solve()
			j=3
			push_back	[1,3,2] *
		swap(2,2)
		j=3
	swap(1,2)			[1,2,3]
	j=3
swap(0,0)
j=1
swap(0,1)				[2,1,3]
solve()
	j=1
	swap(1,1)
	solve()
		j=2
		swap(2,2)
		solve()
			j=3
			push_back	[2,1,3] *
		swap(2,2)
		j=3
	swap(1,1)
	j=2
	swap(1,2)			[2,3,1]
	solve()
		j=2
		swap(2,2)
		solve()
			j=3
			push_back	[2,3,1] *
		swap(2,2)
		j=3
	swap(1,2)			[2,1,3]
	j=3
swap(0,1)				[1,2,3]
j=2
swap(0,2)				[3,2,1]
solve()
	j=1
	swap(1,1)
	solve()
		j=2
		swap(2,2)
		solve()
			j=3
			push_back	[3,2,1] *
		swap(2,2)
		j=3
	swap(1,1)
	j=2
	swap(1,2)			[3,1,2]
	solve()
		j=2
		swap(2,2)
		solve()
			j=3
			push_back	[3,1,2] *
		swap(2,2)
		j=3
	swap(1,2)			[3,2,1]
	j=3
swap(0,2)				[1,2,3]
j=3

The execution flow is from top to bottom. If the code is placed in the second column, it means it is executing the second call of solve, with index equal to 1, ...etc.

Also note how each execution of solve (each column) has its own set of local variables. This means that when j is incremented by the for loop, this doesn't affect the value of j in any other execution context (other column).

I hope this clarifies it.