信息学奥赛一本通 1317：【例5.2】组合的输出

【题目链接】

ybt 1317：【例5.2】组合的输出

【题目考点】

1. 搜索

【解题思路】

解法1：搜索

组合与排列的区别为，组合是一个数字集合，是没有顺序的。
对于排列来说，1 2 3与1 3 2是两种排列。对于组合来说，1 2 3与1 3 2是同一种组合。
如果按搜索全排列的方法来进行搜索，数字相同但顺序不同的情况会多次出现，而我们只需要统计其中的一次。
在相同数字的多种排列中，升序排列一定是唯一的，因而升序排列与组合一定是一一对应的。（例如3 2 1三个数字的升序排列为1 2 3），这里我们就搜索多种排列中的升序排列输出，即可满足题目中“将每个组合按升序顺序输出”的要求。
要保证搜索到的是升序序列，具体写法有两种

• 写法1：当前搜索到的数字要大于等于已经保存的升序排列的最后一个数字
• 写法2：递归时传入遍历的起始值

【题解代码】

解法1：递归

• 写法1：当前数字大于等于升序排列的最后一个数字

#include<bits/stdc++.h>
using namespace std;
bool vis[25];//记录哪些数已经用过
int nums[25];//记录要输出哪些数，记录在num[1],num[2]...,num[r]
int n, r;//从n个元素中抽出r个元素
void dfs(int p)//p:要确定升序排列中的第几个数
{
    
    for(int i = 1; i <= n; ++i)
    {
    
        if(vis[i] == false && i > nums[p-1])//p为初始值1时，取到num[0]，其值为0，已知i都大于0，不影响运行
        {
    
            nums[p] = i;//添加数字 
            vis[i] = true;//数字i已被使用 
            if(p == r)//如果已经填充了r个数字 
            {
    //输出存在num中的排列数
                for(int j = 1; j <= r; ++j)
                    cout << setw(3) << nums[j];
                cout << endl;
            }
            else
                dfs(p+1);
            vis[i] = false;
        }
    }
}

int main()
{
    
    cin >> n >> r;
    dfs(1);
    return 0;
}

• 写法2：递归时传入遍历的起始值

#include<bits/stdc++.h>
using namespace std;
bool vis[25];//记录哪些数已经用过
int nums[25];//记录要输出哪些数，记录在num[1],num[2]...,num[r]
int n, r;//从n个元素中抽出r个元素
void dfs(int p, int st)//p:要确定升序排列中的第几个数，要填入的数字大于等于st
{
    
    for(int i = st; i <= n; ++i)
    {
    
        if(vis[i] == false)
        {
    
            nums[p] = i;//添加数字 
            vis[i] = true;//数字i已被使用 
            if(p == r)//如果已经填充了r个数字 
            {
    //输出存在num中的排列数
                for(int j = 1; j <= r; ++j)
                    cout << setw(3) << nums[j];
                cout << endl;
            }
            else
                dfs(p+1, i);
            vis[i] = false;
        }
    }
}

int main()
{
    
    cin >> n >> r;
    dfs(1, 1);
    return 0;
}