dfs 递归思想解决排列组合的一些基础问题

谁践踏了优雅 2022-08-03 16:58 208阅读 0赞

对于搜索的深度很深或深度不固定的情况，则无法用枚举的方法来设置循环嵌套的层数，这时可以考虑用递归法来完成搜索任务。递归是一种常用算法，它是搜索的另一种实现方式。如果在算法设计中采用一个函数或过程直接或间接地调用它自身来解决问题的方法，则称该方法为递归算法。递归算法必须要设计好一个或若干个确定的递归终止条件。

一......

Sample Input

4 2   //用0,1组合出四个数字来

Sample Output

0000  0001  0010  0011  0100  0101

0110  0111  1000  1001  1010 1011

1100  1101  1110  1111

#include<stdio.h>
    
    int n,m,ans;
    int mat[10];
    
    void solve(int l)
    {
        if(l>=n)
        {
            for(int i=0;i<n;++i)printf("%d", mat[i]);
            puts("");
            ans++;
            return ;
        }
        for(int i=0;i<m;++i)
        {
            mat[l]=i;
            solve(l+1);
        }
    }
    
    int main()
    {
        while(scanf("%d%d", &n, &m)!=EOF)
        {
            ans=0;
            solve(0);
            printf("%d\n",ans);
        }
        return 0;
    }

二全组合排列（没有去重，没有考虑0的问题）

#include<stdio.h>
    #include<string.h>
    
    const int maxn=11;
    int n;
    int used[maxn];//标记数组
    int mat[maxn];//存储数组
    int num[maxn];//输出数组
    
    void solve(int l)
    {
        if(l>=n)
        {
            for(int i=0;i<n;++i)printf("%d", num[i]);
            puts("");
            return;
        }
        for(int i=0;i<n;++i)
        {
            if(!used[i])
            {
                used[i]=1;
                num[l]=mat[i];
                solve(l+1);   //递归
                used[i]=0;    //回溯
            }
        }
    }
    
    int main()
    {
        while(scanf("%d", &n)!=EOF)
        {
            for(int i=0;i<n;++i)
            scanf("%d", mat+i);
            memset(used,0,sizeof(used));
            solve(0);
        }
        return 0;
    }

三非重复组合排列（含重复数字时，生成不重复组合排列，并且0也不能放在首位）

#include <cstdio>
    #include <cstring>
    
    const int maxn = 10;
    int n,v,ans;
    int used[maxn],a[maxn],num[maxn];
    
    void push(int v)
    {
        for(int i = 0 ; i < ans ; i++)
        {
            if(a[i]==v)
            {
                ++used[i];
                return ;
            }
        }
        a[ans]=v;
        ++used[ans++];  //ans为不重复的数字的个数
        //used[i]保存的是i出现的次数
    }
    
    void solve(int l)
    {
        if(l>=n)
        {
            for(int i = 0 ; i < n ; i++)printf("%d",num[i]);
            puts("");
        }
        for(int i = 0 ; i < ans ; i++)
        {
            if(l==0&&a[i]==0)continue;
            if(used[i])
            {
                used[i]--;
                num[l]=a[i];
                solve(l+1);
                used[i]++;
            }
        }
    }
    
    int main()
    {
        while(scanf("%d", &n)!=EOF)
        {
            memset(used,0,sizeof(used));
            ans=0;
            for(int i=0;i<n;++i)
            {
                scanf("%d", &v);
                push(v);
            }
            solve(0);
        }
        return 0;
    }