Description

輸出給定序列按字典序的?�?組合，按照所有?�?個元素出現(xiàn)與否的?01?標記串?����?1,...,�1?的字典序輸出.

此處01串的字典序指：先輸入的數(shù)字對應(yīng)低位，后輸入的數(shù)字對應(yīng)高位，從高位到低位第一個不一樣的位為1的字典序靠后.

Input

第一行集合元素個數(shù)?1≤�≤10?及子集元素個數(shù)?1≤�≤�，第二行?�?個空格隔開的正整數(shù)?1≤��≤100.

Output

每組數(shù)據(jù)輸出所有對應(yīng)的每個組合，每個一行用空格隔開。

Sample

#0

Input

Copy

5 3
3 1 2 4 5

Output

Copy

3 1 2
3 1 4
3 2 4
1 2 4
3 1 5
3 2 5
1 2 5
3 4 5
1 4 5
2 4 5

Hint

樣例中：{3,1,4}表示01011——5(0)4(1)2(0)1(1)3(1)，{1,2,5}表示10110——5(1)4(0)2(1)1(1)3(0)，則{1,2,5}的字典序比{3,1,4}靠后.

題目有點難懂

方法用回溯求組合數(shù)然后排序

#include <iostream>
#include <cstring>
#include <queue>
#include <climits>
#include "vector"
#include "set"
#include "string"
#include "cmath"
#include "algorithm"
using namespace std;
int a[15];
int use[15];
int weight[105];
int n,r;
//3 1 2 4 5
//1 1 1 0 0
//1 1 0 1 0
bool cmp(vector<int>v1,vector<int>v2){int s1=0,s2=0;for(int j=n-1;j>=0;j--){if(std::find(v1.begin(), v1.end(),a[j])!=v1.end()){s1=1;}if(std::find(v2.begin(), v2.end(),a[j])!=v2.end()){s2=1;}if(s1!=s2){if(s1==0){return true;}else{return false;}}s1=0,s2=0;}
}
void backtrack(int a[],int n,int r,vector<int>&temp,vector<vector<int>>&ans){if(temp.size()==r){ans.push_back(temp);return;}for(int i=0;i<n;i++){if(use[i]==0&&((!temp.empty()&&weight[a[i]]<weight[temp[temp.size()-1]])||temp.empty())){use[i]=1;temp.push_back(a[i]);backtrack(a,n,r,temp,ans);temp.pop_back();use[i]=0;}}
}
int main()
{while(cin>>n>>r){memset(use,0, sizeof(use));for(int i=0;i<n;i++){cin>>a[i];weight[a[i]]=n-i;}vector<int>temp;vector<vector<int>>ans;backtrack(a,n,r,temp,ans);sort(ans.begin(),ans.end(), cmp);for(int i=0;i<ans.size();i++){for(int j=0;j<r;j++){cout<<ans[i][j]<<" ";}cout<<endl;}cout<<endl;}return 0;
}