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

Advanced Guide to Algorithm Competition Recursive Implementation of Exponential Enumeration

2022-08-06 17:41:41Early to bed, good body hh

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

思路:for each integer,可以选,也可以不选.The number of all possible scenarios is 2 n 2^n 2n.

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

int n; // n个整数
vector<int> chosen; // selected number

void solve(int x)
{
    
    if (x == n + 1)
    {
    
        for (int i = 0; i < chosen.size(); i++)
        {
    
            printf("%d ", chosen[i]);
        }
        puts("");
        return;
	}
	
    // "不选x"分支
    solve(x + 1);
    
	// "选x"分支
	chosen.push_back(x); // x已被选择
	solve(x + 1);
	chosen.pop_back(); // Restoring the scene before going back to the previous issue
}

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

copyright notice
author[Early to bed, good body hh],Please bring the original link to reprint, thank you.
https://en.cdmana.com/2022/218/202208061720132288.html

Random recommended