组合数(dfs)

淡淡的烟草味﹌ 2022-05-15 01:11 283阅读 0赞

给出一个正整数N，从集合\{1,2,3..N\} 中找出所有大小为k的子集, 并按照字典序从小到大输出。

Input  
第一行是一个整数T,代表T组测试数据。

接下来T行，每行是两个正整数n(1<=n<=10), k(1<=k<=n)。

Output  
对于每组数据按字典序输出所有符合条件的子集。

Sample Input  
1

5 3

Sample Output  
1 2 3

1 2 4

1 2 5

1 3 4

1 3 5

1 4 5

2 3 4

2 3 5

2 4 5

3 4 5  
分析：简单dfs应用,本来想用next\_permutation发现行不通  
**核心代码：**

void dfs(int depth)
    {
        //输出边界
        if(depth==k)
        {
            for(int i=0;i<k-1;i++)
            printf("%d ",a[i]);
            printf("%d\n",a[k-1]);  
        }
        else
        {
        for(int i=1;i<=n;i++)
        {
            bool judge=false;
            for(int j=0;j<depth;j++)
            {
                if(a[j]>=i){
                judge=true;
                break;
                }   
            }
            if(!judge)
            {
                a[depth]=i;
                dfs(depth+1);
            }
        }
      }
    }

**代码总览：**

#include <cstdio>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    int a[20],n,k;
    
    void dfs(int depth)
    {
    
        if(depth==k)
        {
            for(int i=0;i<k-1;i++)
            printf("%d ",a[i]);
            printf("%d\n",a[k-1]);  
        }
        else
        {
        for(int i=1;i<=n;i++)
        {
            bool judge=false;
            for(int j=0;j<depth;j++)
            {
                if(a[j]>=i){
                judge=true;
                break;
                }   
            }
            if(!judge)
            {
                a[depth]=i;
                dfs(depth+1);
            }
        }
      }
    }
    int main()
    {
        int t;
        scanf("%d",&t);
        while(t--){
            scanf("%d%d",&n,&k);
            for(int i=0;i<n;i++)
            a[i]=i+1;
            dfs(0); 
        }
        return 0;
    }

做了一些题目 对递归主要是掌握**递归边界 递归条件 递归返回的位置** 另外手工模拟对理解题意也很重要