代码源每日一题div2 可重排列

可重排列 - 题目 - Daimayuan Online Judge

题意：

按字典序从小到大，输出所有序列，满足其中有p1个1, p2个2, ……, pn个n。

思路：

一眼输出全排列

第一次写的时候还对于每一次全排列，都恢复一下map的值

实际上没有必要，因为回溯的过程中自动恢复了

Code：

#include 
using namespace std;
const int mxn=10;
int n,sum=0;
int p[mxn];
unordered_map<int,int> mp;
vector<int> ans;
void print(){
    for(int i=0;i<=sum-1;i++) printf("%d%c",ans[i],i==sum-1?'\n':' ');
}
void dfs(int dep){
    if(dep>sum){
        print();
        return;
    }
    for(int i=1;i<=n;i++){
        if(mp[i]){
            mp[i]--;
            ans.push_back(i);
            dfs(dep+1);
            mp[i]++;
            ans.pop_back();
        }
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {scanf("%d",&p[i]),sum+=p[i];mp[i]=p[i];}
    dfs(1);
}

方法2：学一学全排列的stl（待补