深圳技术大学oj C : 生成r子集

Description

输出给定序列按字典序的 � 组合，按照所有 � 个元素出现与否的 01 标记串 ����−1,...,�1 的字典序输出.

此处01串的字典序指：先输入的数字对应低位，后输入的数字对应高位，从高位到低位第一个不一样的位为1的字典序靠后.

Input

第一行集合元素个数 1≤�≤10 及子集元素个数 1≤�≤�，第二行 � 个空格隔开的正整数 1≤��≤100.

Output

每组数据输出所有对应的每个组合，每个一行用空格隔开。

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}靠后.

题目有点难懂

方法用回溯求组合数然后排序

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