Informatics Aosai yibentong 1317: [example 5.2] combined output

【 Topic link 】

ybt 1317：【 example 5.2】 Combined output

【 Topic test site 】

1. Search for

【 Their thinking 】

solution 1： Search for

The difference between combination and arrangement is , A combination is a set of numbers , There is no order .
For permutations ,1 2 3 And 1 3 2 There are two permutations . For combinations ,1 2 3 And 1 3 2 It's the same combination .
If you search by the method of full ranking , The same number but in different order will occur many times , And we only need to count one of them .
In multiple permutations of the same number , Ascending order must be unique , Therefore, the ascending arrangement and combination must be one-to-one correspondence .（ for example 3 2 1 The ascending order of the three numbers is 1 2 3）, Here we will search for the ascending order output in various permutations , It can meet the requirements of “ Output each combination in ascending order ” The requirements of .
Make sure you find an ascending sequence , There are two specific ways to write

• How to write it 1： The number currently searched must be greater than or equal to the last number in the saved ascending order
• How to write it 2： The starting value of traversal is passed in during recursion

【 Solution code 】

solution 1： recursive

• How to write it 1： The current number is greater than or equal to the last number in ascending order

#include<bits/stdc++.h>
using namespace std;
bool vis[25];// Record which numbers have been used 
int nums[25];// Record which numbers to output , Recorded in the num[1],num[2]...,num[r]
int n, r;// from n Out of these elements r Elements 
void dfs(int p)//p: To determine the number in ascending order 
{
    
    for(int i = 1; i <= n; ++i)
    {
    
        if(vis[i] == false && i > nums[p-1])//p For the initial value 1 when , Fetch num[0], Its value is 0, It is known that i Is greater than 0, No impact on operation 
        {
    
            nums[p] = i;// Add numbers  
            vis[i] = true;// Numbers i Used  
            if(p == r)// If it has been filled r A digital  
            {
    // The output exists num Number of permutations in 
                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;
}

• How to write it 2： The starting value of traversal is passed in during recursion

#include<bits/stdc++.h>
using namespace std;
bool vis[25];// Record which numbers have been used 
int nums[25];// Record which numbers to output , Recorded in the num[1],num[2]...,num[r]
int n, r;// from n Out of these elements r Elements 
void dfs(int p, int st)//p: To determine the number in ascending order , The number to be filled in is greater than or equal to st
{
    
    for(int i = st; i <= n; ++i)
    {
    
        if(vis[i] == false)
        {
    
            nums[p] = i;// Add numbers  
            vis[i] = true;// Numbers i Used  
            if(p == r)// If it has been filled r A digital  
            {
    // The output exists num Number of permutations in 
                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;
}