全排列问题

全排列问题

• $[l-r]$间数字的全排列问题

extern int ans[MAX],l,r;
bool ret[MAX];
void dfs(int l,int r){
    if(l==r+1){
        for(int i=1;i<=r;i++) cout<<ans[i]<<' ';
        cout<<endl;
    }else
        for(int i=l;i<=r;i++)
            if(!ret[i]){
                ans[l]=i,ret[i]=1;
                dfs(l+1,r);
                ret[i]=0;//回溯
            }
}

• 数组元素$[l,r]$区间全排列问题

extern int a[MAX],num;//num:方案数
int dfs(int l,int r){
    if(l==r){
        num++;
        for(int j=0;j<MAX;j++) cout<<a[j]<<' ';
        cout<<endl;
    }else{
        for(int i=l;i<r;i++){
            swap(a[l],a[i]);
            dfs(l+1,r);
            swap(a[l],a[i]);//回溯
        }
    }
    return num;
}