Posted on |

pre&in-order input

leetCode105 : given preorder and inorder traversal of a tree, construct the binary tree.

sol: each top node in Btree, has left-branch and right-branch, and each branch is a similar-structure subtree. so every time pop out the top node, and recursive the two subtrees, which return as the left kid and right kid of current top node.

the recursive stopped when the list is empty(in real case, this means the node has only either left or right kid); or stopped when only one element in the list(in real case, the node has both kids, so left or right subtree has only one element).

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
28
29
30
31
32
33
34
35
36
37
TreeNode* sol(list<int>& pre,  list<int>& in)
 {
	 if(pre.empty() || in.empty())
	 {
		 return nullptr; //empty left/right node 
	 }
	 
	 if(pre.size() == 1 && in.size() == 1) 
	 {
			 return new TreeNode(pre.front());
	 }
	 
	 int root = pre.front(); 
	 pre.pop_front(); 
	 TreeNode* root_node = new TreeNode(root); 
	 list<int>::iterator in_it, pre_it; 
	 in_it =  std::find(in.begin(), in.end(), root);
	 if(in_it == in.end()) //only one node in inorder list now, wont happen
	 {
		return (new TreeNode(in.front()));
	 }
	 int idx =  std::distance(in.begin(), in_it);
	 list<int> in_left_subtree(in.begin(), in_it);
	 list<int> in_right_subtree(++in_it, in.end());	
	 in.erase(in_it);
	 
	pre_it = pre.begin(); 
	std::advance(pre_it, idx); 
	
	list<int> pre_left_subtree(pre.begin(), pre_it); 
	list<int> pre_right_subtree(pre_it, pre.end()); 	
	
	root_node->left = sol(pre_left_subtree, in_left_subtree);
	root_node->right = sol(pre_right_subtree, in_right_subtree);
	return root_node; 	 
 }

in each recursive step, I am using exteral containers, same stragey in scramble string. is there a one-swap way?

post/in-order input

leetCode106

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
28
29
TreeNode*  sol(list<int>& in,  list<int>& post)
{
	if(in.empty() || post.empty())
		return nullptr; 
	
	if(in.size() == 1 || post.size() == 1)
		return (new TreeNode(in.front())); // return the left || right kid 
	
	//first find out the tree root, the last element in post-order 
	int root_v =  post.back();
	TreeNode* root = new TreeNode(root_v); 
	post.pop_back(); 
	//find root_v in  inorder 
	list<int>::iterator  in_lit =  std::find(in.begin(), in.end(), root_v); 
	
	//create subtrees recursive 
	int left_length =  std::distance(in.begin(), in_lit); 
	list<int> in_left_sub(in.begin(), in_lit); 
	list<int> in_right_sub(++in_lit, in.end()); 
	in.erase(in_lit); 
	list<int>::iterator post_lit = std::next(post.begin(), left_length); 
	list<int> post_left_sub(post.begin(), post_lit);
	list<int> post_right_sub(post_lit, post.end()); 
	
	root->left = sol(in_left_sub, post_left_sub); 
	root->right = sol(in_right_sub, post_right_sub);
	return root ;
}

Posted on |

first there should be a queue or stack to store the next layer elements, as the tree go deeper, there are many branches, which requires a contianer to track what’s the elements in next layer. stack always pop out the top element(FILO), which actually set the input elements in a reversed order as tree elements; queue can pop out the first element(FIFO), which can set the input elements in the same order in tree elements. so here pick std::queue.

the input array can used std::vector, each time pop_front(), which basically read the array in order. and each pop_front element constructs a new TreeNode. if the layer container is empty(), then it’s the root layer; else it’s a branch layer. growing the tree in each branch layer, need update the next layer container.

for each new inserting element, either insert to left or right of node A in parent layer or insert to the A’s sibling node B. then pop out the node which already has both kids.

when traversling to the last node in parent layer, and if both the kids are filled-in, then there is a turning point, need to swap next_parent layer as parent layer.

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
void insert_kids(std::queue<TreeNode*>& parents, std::queue<TreeNode*>& next_parents, TreeNode* p)
{
	if(parents.empty())
		return ;
	TreeNode* father = parents.front();
	if(!father->left)
	{
		father->left = p;
		if(p)
			next_parents.push(p);
	}else if(!father->right)
	{
		father->right = p;
		if(p)
			next_parents.push(p);
	}else
	{
		parents.pop(); 
		if(parents.empty())  // turning point, if returned then p will be lost 
		{
			parents.swap(next_parents);  
		}		
		insert_kids(parents, next_parents, p); 	}	
}
TreeNode* breadth_construct(list<int>& arr)
{
	TreeNode *p, *root ; 
	int x ; 
	std::queue<TreeNode*> parents, next_parents; 
	
	while(!arr.empty())
	{
		x = arr.front();	
		arr.pop_front();
		
		p = (TreeNode*) new TreeNode(x); 
			
		if(parents.empty())
		{
			parents.push(p);
			root = p ; 
			continue; 
		}else if( !parents.empty())  //at this step, parents still has 1 element, but after insert_kids, parents is empty. then 
		{
			insert_kids(parents, next_parents, p); 
			continue;
		}
	}
	return root; 
}

how to deal with NULL during struct constructure? if both (int x) and (TreeNode* p) constructor are defined, which will lead to ambisious when new TreeNode(NULL).

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
struct TreeNode {
	int value ;
	struct TreeNode *left ;
	struct TreeNode *right;
	//TODO: how to implement copy assignment in structure ?
	TreeNode(TreeNode* p)
	{
		if(p == NULL)
		{
			value = 0;
			left = NULL;
			right = NULL;
		}else
		{
			value = p->value;
			left = p->left;
			right = p->right; 
		}
	}
	TreeNode(int x):
		value(x), 
		left(NULL),	
		right(NULL)
		{
		}
};

Posted on |

combinatorics related algorithms e.g. unique BST(leetCode95), Permutations(46), Unique Path(62). Give an integer m, how many different combinations can have? mathematically, it’s a permutation P_m^m or combination C_m^n problem, the total number is easy to calculate, but how to write a code to print out each combination elegantly ?

one core step: how to generate a new combination(k+1) array by inserting one new element into the current combination(k). e.g. 

{1, 2} --> {3, 1, 2}, {1, 3, 2}, {1, 2, 3}

here is basically insert 3 at (k+1) positions, and each new position will generate a new combination with (k+1) size. depends on the problem, choose either vector(to support random access) or list (to support O(1) insert or delete) as the container.

one tip here, how to erase one element from std::list while iterating ?

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
vector<list<int>>  next_layer(vector<list<int>>& layer, int c)
{
	if(layer.empty())
	{
		list<int> tmp ;
		tmp.push_back(c);
		layer.push_back(tmp);
		return layer;
	}
	
	vector<list<int>> next_layer_v, cur; 
	for(int i=0; i<layer.size(); i++)
	{
		list<int>::iterator lit ;
		list<int>  arr = layer[i] ; 
		cur.clear();
		for(lit = arr.begin(); lit != arr.end(); lit++)
		{
 			arr.insert(lit, c); //insert c in front of lit
   			cur.push_back(arr);
   			lit = arr.erase(--lit);  // erase c, which is 1 step in front of lit, and must return lit here, else lit will become non-refereable 
		}
	
	 	next_layer_v.insert(next_layer_v.end(), cur.begin(),  cur.end()); 
	}
	
	return next_layer_v; 
}
void sol(int num)
{
  vector<list<int> > layer, last_layer;
  list<int>  cur_list ;
  for(int i=0; i< num; i++)
  {
	  layer = next_layer(last_layer, i);
	  last_layer = layer;
  }
  print_vec_list(layer);
}

this implementation is more clear than what I did in Permutation

while the memory of many last layers vector> actually are not in using. how to recycle the memory ?

1
2
3
4
vector<list<int>>().swap(layer);
//or -std=c++11
layer.resize(0);
layer.shrink_to_fit();

Posted on |

construct an object

the compiler will define a default constructor with no parameters, if there is no user defined default constructors. usually the parameters for user defined(UD) default constructors should have default values.

directly call the UD constructor will create an object; call the UD through new keyword will create an object pointer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct TreeNode{
	int val; 
	TreeNode *right ;
	TreeNode *left;
	TreeNode(int x=0): val(x), left(NULL), right(NULL){}; //user defined constructor 
	TreeNode(const TreeNode *cp) //copy constructor 
	{
		val = cp->val;
		right = cp->right;
		left = cp->left;
	}
}
TreeNode node1; 
TreeNode node2(100);
TreeNode *node_p = new TreeNode(10);

create an object in pure C

new operator do two things: allocate memory for a C++ class object, then call the object’s constructor to initialize this object. basically, new packages memory management of objects and objects initialization.

while in pure C, since there is no object constructor, after malloc memory for the structure, either call an initial function or manually initialize this structure member variables.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
TreeNode 
{
	int val; 
	TreeNode *right ;
	TreeNode *left;
}
int main()
{
   TreeNode *p =  (TreeNode*) malloc( sizeof(struct TreeNode)); 
   p->val = 0;
   p->right = NULL; 
   p->left = NULL ; 
}
``` 
  
## construct an object array 
beyond creating one object (pointer), how to create object array.  
```c 
int nums = 5;
TreeNode tree_array[nums];
TreeNode *tree_p = (TreeNode*) new TreeNode[nums];

be aware, each element in tree_array has the whole memory of TreeNode structure; and tree_p++ will go to next TreeNode structure, tree_p[i] is also a whole memory of TreeNode structure.

create an object array in pure C

1
2
int nums = 5;
TreeNode *tree_p = (TreeNode*) malloc(nums * sizeof(TreeNode));

basically malloc will return a pointer to a block of memory, but it’s not responsible to initialize this block of memory.

the rule of five

rule of three is about how to manage dynamically allocated resources in C++.

why it is necessary?

1) when parameter B is copying by value from A, if no user defined copy constructor, the compiler will do a shallow copy from A to B by default, in which a new pointer point to the same content address. at the end of function call, the parameter B is out of scope, so destructor is called, and A is still there. but at the end of the main function, A is out of scope, need deallocating, then error is B already deallocate the content of A.

with a user defined copy constructor, B will get a deep copy of A, so no sharing content, no problems when deallocating either B or A.

2) if no user specified assignment constructor, a shallow copy happens, then error-potential. and assignment constructor (operator=) can be implemented with copy constructor. 

1
2
3
4
5
6
7
int main()
{
	TreeNode node1;
	TreeNode node2 = node1; //actually a copy-construct, same as node2(node1)
	TreeNode node3 ;
	node3 = node1 ; //a compiler assignment-construct by default(shallow copy)
}

Posted on |

scramble string at leetCode 87. sol: get all possible scrambled strings of s1, then compare if s2 is in it.

for 1-char:   scramble("a") --> "a" 
    for 2-chars :  scramble("ab") --> "ba"  
for 3-chars:  scramble("abc") --> "bac", "cba",  "acb", "cba"      for 4-chars:   scramble("abcd") -->  (a | bcd) + (ab | cd) +  (abc | d) 
for 5-chars:  scramble("abcde") --> (a | bcde) +  (ab | cde) +  (abc |  de) + (abcd | e)

from the enumaration, there is always a left-substring and a right-substring, and recursive in each substring. consider the push_back order, there are two: left->\right and right->\left at each two slibings.

additional routines: how to do substring join and how to delete duplicate string from string-vector.

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
 string join(string& sub1, string& sub2)
 {
	 string res; 
	 res.reserve(sub1.size() + sub2.size());
	 
	 string::iterator it;
	 
	 for(it = sub1.begin(); it != sub1.end(); it++)
		 res.push_back(*it);
	 
	 for(it = sub2.begin(); it != sub2.end(); it++)
		 res.push_back(*it);
	 
	 return res;
 }
 
 //TODO:  keep in mind the transfer function, and how to design it  
 vector<string>  scramble(string& s)
 {
	 string  ls, rs; 
	 vector<string> vls, vrs, vcurs; 
	 
	 if(s.size() == 1)
	 {
		 vcurs.push_back(s); 
		 return vcurs; 
	 }
	 
	 for(int i=1; i<s.size(); i++)
	 {
		 ls = s.substr(0, i);
		 rs = s.substr(i, s.size()); 
		 vls = scramble(ls);
		 vrs = scramble(rs); 		 
		 
		 for(int m=0; m< vls.size(); m++)
			 for(int n=0; n < vrs.size(); n++)
			 {				 
				 vcurs.push_back(join(vls[m], vrs[n])); 
				 vcurs.push_back(join(vrs[n], vls[m])); 			 
			 }
	 }
/*how to delete duplicated string from vector<string> */ 	 
	 std::sort(vcurs.begin(), vcurs.end()); 
	 vcurs.erase( std::unique(vcurs.begin(), vcurs.end()), vcurs.end()); 
	 return vcurs; 
 } 
int main()
{
	string s1 = "abcd" ;
	vector<string> outs = scramble(s1); 
	for(int i=0; i<outs.size(); i++)
		cout << outs[i] << endl; 
	return 0;
}

How to write a completed code, meaning, always take care the boundaries correctly, no missing situations. It’s easy to start from scratch and achieve somewhere, but hard to be completed.

Posted on |

leetcode 64(Mini Path Sum): Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

the first thought is to build a tree：

     1
     /        \
  1       3 
 / \     / \
4   5   1   5
/  /\   /   /\
2  1 2  1   1 2

while this is not a balanced tree, no regular tree way to maintain. Then what else solution? Dynamic Programming is a strategy to solve a simple problem at first, then find the rules(status transfer from previous state to current state) for the remaining problems.

step1: the simpler problem, or as initial/boundary condition. e.g. only one row, or only one col, what’s the solution.

step2: in general m rows, n cols, how to get the iterative rules after step1.

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
28
29
30
31
32
33
34
35
36
37
38
39
int sol(vector<vector<int> >& mat)
{
	vector<vector<int> > dp; 
	
	int row = mat.size();
	int col = mat[0].size(); 
	
	for(int i=0; i<row; i++)
		dp[i][0] += mat[i][0];
    for(int j=0; j<col; j++)
		dp[0][j] += mat[0][j];
	
	for(int i=1; i<row; i++)
		for(int j=1; j<col; j++)
			dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + mat[i][j]; 
	
	return dp[row-1][col-1]; 
}
int main()
{
 vector<int> v1, v2, v3 ;
 v1 = {1, 3, 1};
 v2 = {1, 5, 1};
 v3 = {4, 2, 1}
 
 vector<vector<int> >   mat;
 mat.push_back(v1);
 mat.push_back(v2);
 mat.push_back(v3);
 
 int out = sol(mat);
 
 cout << "output =" << out << endl; 
 
 return 0;
}

See DP solution is much clear than design the tree.

Posted on |

leetCode 62(unique paths):
A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below). How many possible unique paths are there?

solution: it’s easy to model as a math combination problem, assume the right-step has m; the down-step has n. so each path from top left to bottom right, has (m+n) steps totally. the total unique paths is C_(m+n)^m

passing by value: 

1
2
3
4
5
int sol(int rm, int rn)
{
  return rm==0 ? 1 : (rm+rn)/rm * sol(rm-1, rn);
}

what happened if rm-1 changed to rm–? 

warning: unsequenced modification and access to 'rm'

what about passing as reference ? 

1
2
3
4
int sol(int& m, int& n)
{
  return m==0 ? 1 : (m+n)/(float)m * sol(--m, n);
}

if using m– :

error:  expects an l-value for 1st argument of sol(int&, int&)

m– is only r-value, can’t be used as reference varaible; but –m is r-value.

for m as a reference variable, –m is the way to update the content of the address. while m– more like move to the next address?

Posted on |

leetCode 50 (N-Queens):
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

solution: each potentional position for a queen should satisfy no attach, then traverse the 2D grids to find out all good positions; it requires to find all possible combinations, so recursive call will be used also.

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
 bool one_queen_visited(int** mat, int n, pair<int, int>& queen_idx)
 {
	 int row = queen_idx.first ;
	 int col = queen_idx.second; 
	 
	 for(int i=0; i<n; i++)
	 {
		for(int j=0; j<n; j++)
		{
			if(mat[row][j] == 0)
				mat[row][j] = 1;
			else if(mat[row][j] == 100)
				return false; 
		}
		
		if(mat[i][col] == 0)
			 mat[i][col] = 1;
		else if(mat[i][col] == 100)
			 return false; 
	 }
		
	 //for left leaning 
	 for(int i=row, j=col; i>=0 && j>=0; i--, j--)
	 {
			if(mat[i][j] == 0)
				mat[i][j] = 1; 
			else if(mat[i][j] == 100)
				return false; 
	 }
	 
	 for(int i=row, j=col; i<n && j<n; i++, j++)
	 {
			if(mat[i][j] == 0)
				mat[i][j] = 1; 
			else if(mat[i][j] == 100)
				return false; 
	 }	
	  
	 //for right leaning 
		//down
	  for(int i=row, j=col; i<n && j>=0; i++, j--)
	 {
			if(mat[i][j] == 0)
				mat[i][j] = 1; 
			else if(mat[i][j] == 100)
				return false; 
	 }
	  //up 
	 for(int i=row, j=col; i>=0 && j<n; i--, j++)
	 {
			if(mat[i][j] == 0)
				mat[i][j] = 1; 
			else if(mat[i][j] == 100)
				return false; 
	 }	
 
	 mat[row][col] = 100;  //queen location marked as 100
	 return true; 
 }
int backtrack = 0; 
	 
void sol(int** mat,  int n, int start_j=0)
 {
	 std::pair<int, int>  idx; 
	 vector<pair<int, int>>   queens; 
	 vector< vector<pair<int, int>> >  queens_v; 
	 if(start_j > n) return ;   //end of recursive 
	 for(int i=0; i<n; i++)
	 {
		 for(int j= ((i==0)? max(start_j, 0) : 0); j<n; j++)
		 {
			 idx =  std::make_pair(i, j); 
			 if(one_queen_visited(mat, n, idx)) // find a fit queen position, store into  queens 
			 {
				 queens.push_back(idx);
			 }
		 }
	 } 
	 	 
	 if(queens.size() == n)
	 {
		 queens_v.push_back(queens);
		int** mat_copy =  new int*[n] ;
		for(int i=0; i<n; i++)
		{
			mat_copy[i] = new  int[n](); 
		}	
	
		for(int i=0; i<queens.size(); i++)
		{
			idx =  queens[i];
			mat_copy[idx.first][idx.second] = 1 ;
		}
	
		for(int i=0; i<n; i++)
		{
			for(int j=0; j<n; j++)
				cout<< mat_copy[i][j] << ' ' ;
			cout << endl;
		}
	 }
		
	clean_mat(mat, n);
	sol(mat, n, ++backtrack); 			
 }

I did actually new memory in C++ as following:

1
2
3
int** mat = (int**) new(n * sizeof(int*)); 
for(int i=0;  i<n; i++)
	mat[i] = (int*) new( n * sizeof(int));

which failed, then realized only malloc works in this way.

Posted on |

leetCode 45 (jump game): Given an array of non-negative integers, you are initially positioned at the first index of the array.Each element in the array represents your maximum jump length at that position.Your goal is to reach the last index in the minimum number of jumps.

e.g. [2, 3, 1, 1, 4] –> 2

solution: at current position, bfs all the next positions it can jump to, when the back element is in next position list, then reached.

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
int sol(vector<int>& nums )
{
	vector<int>::iterator  it, cur_it ;
	vector<int> *adj = new vector<int>[nums.size()]; 	
	int cur_node ; 
	for(it=nums.begin(); it < nums.end();  it++)
	{
		cur_node = *it; 
		adj[cur_node].push_back(cur_node); 
		for(int i=1; i<=cur_node; i++)
		{
			cur_it =  std::next(it, i);
			adj[cur_node].push_back(*cur_it); 
			if( *cur_it == nums.back()){
				it = nums.end();  //reach the last element, so return 
			}
		}
	}
	
	vector<int> tmp; 
	int last_element = nums.back(); 
	int mini_path = 1; 
	for(int i=0; i < nums.size(); i++)
	{
		tmp = adj[i]; 
		if(!tmp.empty())
		{ 
			for(int j=0; j<tmp.size(); j++)
			{
				cout<< tmp[j] << ' ' ;
			}
			cout << endl; 
			if(tmp.back() == last_element)
			{
				return mini_path; 
			}
			mini_path++; 
		}
	}	
	return -1;
}

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;
}