how recursive works

Posted on |

leetCode 46 Permutations: given a collection of distinct integers, return all possible permutations.

Input: [1, 2, 3]

Output:
[ [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3, 1,2], 
[3,2,1] ]

At first glipmse, it’s middle difficult, jump to recursive implementation. But there always confused failures, e.g. passing vector as reference to the recursive calls, and even do a deep copy of that vector, the base vector is always modified by the copied vector. This problem blocks me a whole day, actually I don’t know how to make a recursive calls work.

tip1) each recursive fun has its independent local variables ;

tip2) recursive calls are serialized, namely only when inside recursive fun is done, then the outside recursive will continue.

tip1 helps to explain when local variables changed unexpected; tip2 helps cause I trend to think all recursive calls are parallezed running, but the real running order is serialized, so no twist.

simulate how human brain solve this problem:

<1(fix), 2(fix), 3> ;  <1(fix), 3(fix), 2> …

the first position has n potentional values, then the second position has (n-1) potentional values, etc. so design the very first implementation as: traverse all potentional values in first position, and push it; then travers all potentional values in next position, and push it; till the last position, while only one element left, and push it. so a new combination is created. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
vector<vector<int>> sol1(vector<int>& nums)
{
	vector<vector<int>> idx_vector ;
		
	for(int i=0; i< nums.size(); i++) 
	{
		vector<int> tmp ;
		tmp.push_back(nums[i]);  //the first element in new created vector 
		vector<int> nums1 =  nums ;
		nums1.erase(nums1.begin()+i);  //the second element in new created vector  
		for(int j=0; j< nums1.size(); j++)
		{
			tmp.push_back(nums1[j]);
			vector<int> nums2 = nums1; 
			nums2.erase(nums2.begin() + j);
			if(nums2.size() == 1)
			{
					tmp.push_back(nums2[0]);
					idx_vector.push_back(tmp); 	
					tmp.pop_back();
			}
		tmp.pop_back(); 
		}	
	}
	
	return idx_vector; 
}

the first implmenation only works for fixed input <1, 3="" 2,="">, so how to design a recursive fun to make this idea more general ? it’s easy to abstract the process above: for ith position in the new combination vector, the potentional values is one less from (i-1)th position, traverse all possible values in ith position and push it, don’t forget pop it out for traversing to the next possible value; and the end of recursive is when only one element left.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void sol(vector<int>& nums, vector<int>& tmp, vector<vector<int>>& idx_vector )
{
	if(nums.size() == 1)
	{
		tmp.push_back(nums[0]);
		idx_vector.push_back(tmp);
		tmp.pop_back();
		return ;
	}
		
	for(int i=0; i< nums.size(); i++)
	{
		tmp.push_back(nums[i]);
		vector<int> nums2 = nums; 
		nums2.erase(nums2.begin()+i);
		sol(nums2, tmp, idx_vector);
		tmp.pop_back();
	}
	
	return;
}

test:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int main()
{
	vector<int> nums = {1, 2, 3, 4}; 	
	int size =  nums.size(); 
	vector<int> tmp ;
	vector<vector<int>> outs;
	sol(nums, tmp, outs);
	
	vector<int>::iterator it ;
	for(int i=0; i< size*(size-1); i++)
	{
		for(it = outs[i].begin();  it != outs[i].end(); it++)
			cout<< *it << ' ' ; 
		cout << "\n" << endl ;
	}
	
	return 0;
}