文章

3

粉丝

143

获赞

2

访问

21.2k

头像
全排列(dfs)

#include<iostream>
#include<string>
using namespace std;

const int N=10;
char s[N], res[N];
bool used[N];

void dfs(int u, int len)
{
    if(u==len)
    {
        for(int i=0;i<len;i++)
            cout<<res[i];
        cout<<endl;
        return;
    }
    for(int i=0; i<len; i++)
        if(!used[i])
        {
            res[u]=s[i];
            used[i]=true;
            dfs(u+1, len);
            used[i]=false;
        }
}

int main()
{
    cin.tie(0);
    string str;
    cin>>str;
    for(int i=0; i<str.size(); i++)    s[i]=str[i];
    dfs(0, str.size());
    return 0;
}

dfs需要注意的两个问题

回溯:递归结束后需还原

剪枝:为减少递归次数,需要设置情况限制

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发