current position:Home>Advanced Guide to Algorithm Competition Recursive Implementation of Permutation Enumeration

Advanced Guide to Algorithm Competition Recursive Implementation of Permutation Enumeration

2022-08-06 17:39:43Go to bed early and feel good hh

题目链接:https://ac.nowcoder.com/acm/contest/998/C

思路:Enumeration on each position which number.

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 20;

int n; // n个整数
bool used[N]; // If mark integer had been selected
int path[N]; // In order to record the selected integer

void solve(int idx)
{
    
    if (idx == n + 1)
    {
    
        for (int i = 1; i <= n; i++)
        {
    
            printf("%d ", path[i]);
        }
        puts("");
        return;
	}
	
	for (int i = 1; i <= n; i++)
	{
    
	    if (used[i]) continue;
	    
	    used[i] = true;
	    path[idx] = i;
	    
		solve(idx + 1);
		
		used[i] = false;
		path[idx] = 0; // 这一行可以省略
	}
}

int main()
{
    
    scanf("%d", &n);
    
    solve(1);
    
    return 0;
}

copyright notice
author[Go to bed early and feel good hh],Please bring the original link to reprint, thank you.
https://en.cdmana.com/2022/218/202208061720132197.html

Random recommended