学步园

这是G家的面试题：

首先给你一个字符序列，比如 2,1 5,4 6 

然后让你生成这么一个序列 ，其中  s1 < s2 >s3 < s4 >s5 <s6 ....

这个还比较好说咯，把原来的序列排序，然后把后一半的数字插入到前一半的中间，就能得到了。

你以为就完了吗，当然没有。

接着会问你，怎么把全部的这种序列排出来。

巧妙的生成我还想不到，我就用了个比较直观暴力的回溯来做了，每次选取一个没用过的数字到当前位置就好了。

#include<iostream>
#include<iterator>
#include<vector>
#include<algorithm>
using namespace std;

void print(vector<int>& nums,vector<int>& cur,vector<int>& used);
void printInterwineSeq(vector<int>& nums)
{
	if(nums.empty())
		return;
	sort(nums.begin(),nums.end());
	vector<int> cur;
	vector<int> used(nums.size(),0);
	print(nums,cur,used);
}
void print(vector<int>& nums,vector<int>& cur,vector<int>& used)
{
	if(cur.size()==nums.size())
	{
		copy(cur.begin(),cur.end(),ostream_iterator<int>(cout," "));
		cout<<endl;
		return;
	}
	int k=cur.size()+1;
	for(size_t i=0;i<nums.size();i++)
	{
		if(used[i])
			continue;
		if((k&1)&&(k==1||nums[i]<cur.back()))
		{
			used[i]=1;
			cur.push_back(nums[i]);
			print(nums,cur,used);
			cur.pop_back();
			used[i]=0;
		}
		else if ((k%2==0)&&nums[i]>cur.back())
		{
			used[i]=1;
			cur.push_back(nums[i]);
			print(nums,cur,used);
			cur.pop_back();
			used[i]=0;
		}
	}
}
int main()
{
	int n;
	while(cin>>n&&n)
	{
		vector<int> num(n,0);
		for(int i=0;i<n;i++)
			cin>>num[i];
		printInterwineSeq(num);
	}
}

怎么样，是不是跟subsets很像？ 当然了，回溯都长的差不多。

好了，再追问一个？ 如果可以有重复元素怎么办？ 而且序列把小于变成小于等于，大于变成大于等于？

再联系下subsets II  不就是了~ 

#include<iostream>
#include<iterator>
#include<vector>
#include<algorithm>
using namespace std;

void print(vector<int>& nums,vector<int>& cur,vector<int>& used);
void printInterwineSeq(vector<int>& nums)
{
	if(nums.empty())
		return;
	sort(nums.begin(),nums.end());
	vector<int> cur;
	vector<int> used(nums.size(),0);
	print(nums,cur,used);
}
void print(vector<int>& nums,vector<int>& cur,vector<int>& used)
{
	if(cur.size()==nums.size())
	{
		copy(cur.begin(),cur.end(),ostream_iterator<int>(cout," "));
		cout<<endl;
		return;
	}
	int k=cur.size()+1;
	for(size_t i=0;i<nums.size();i++)
	{
		if(used[i])
			continue;
		if(i!=0&&nums[i]==nums[i-1]&&!used[i-1])
			continue;
		if((k&1)&&(k==1||nums[i]<=cur.back()))
		{
			used[i]=1;
			cur.push_back(nums[i]);
			print(nums,cur,used);
			cur.pop_back();
			used[i]=0;
		}
		else if ((k%2==0)&&nums[i]>=cur.back())
		{
			used[i]=1;
			cur.push_back(nums[i]);
			print(nums,cur,used);
			cur.pop_back();
			used[i]=0;
		}
	}
}
int main()
{
	int n;
	while(cin>>n&&n)
	{
		vector<int> num(n,0);
		for(int i=0;i<n;i++)
			cin>>num[i];
		printInterwineSeq(num);
	}
}