---

title: 遞歸實現指數型枚舉
date: 2023-12-10 19:29:20
tags: 遞歸
catgories: 算法進階指南

—> 傳送門

題目大意

從 1 ~ $n$ 這 $n$ 個整數隨機選取任意多個，輸出所有可能的選擇方案

思路

這等價于每個整數可以選或者不選，所有的方案總數共有 $2^n$ 種。我們用遞歸來進行求解。在每一次的遞歸當中分別嘗試 選 或者 不選 兩條分支，將尚未確定的整數數量減少 $1$，從而轉化為一個規模更小的同類問題

時間復雜度

$2^n$

#include<bits/stdc++.h>
using namespace std;typedef long long LL;const int N = 1e5 + 10;pair<string,int> a[N];
int n;
vector<int> vec;
void calc(int x)
{if(x == n + 1){for(auto v : vec) cout << v << ' ';cout << endl;return;}calc(x + 1);//不選vec.push_back(x);calc(x + 1);//選vec.pop_back();//還原現場
}
int main()
{cin >> n;calc(1);return 0;
}