1207: 字符排列问题 C++ STL容器 深度优先搜索DFS

解题思路:

注意事项:

参考代码:

#include<bits/stdc++.h>
using namespace std;
map<char,int>m;         //对排列中的字符进行查重
set<string>Set_;        //对字符串排列进行查重
string s="";
int ans=0;
int num;
    void dfs(int index){
        if(index>=num&&Set_.count(s)==0){
            Set_.insert(s);
            //cout<<s<<endl;
            ans++;
            return;
        }
        for(auto i=m.begin();i!=m.end();i++){    //对map中出现过的字符进行遍历
            if(i->second<=0){                    //如果字符出现次数为0,跳过这次循环
                continue;
            }
            s+=i->first;
            i->second--;                         //将字符出现的次数减去1
            dfs(index+1);                        //进入下一层搜索
            s.erase(s.length()-1);               //删除叶子节点元素
            i->second++;
        }
    }
main(){
    string temp;
    cin>>num;
    cin>>temp;
    for(int i=0;i<num;i++){
        m[temp[i]]++;                            //用map统计字符
    }
    dfs(0);
    cout<<ans;
}