e942 - pC. 數字排列
題目描述
題目要求給定 N 個相異的正整數，輸出所有可能的排列組合，且排列組合需按照數字大小順序輸出。
解題思路
本題的核心在於產生所有可能的排列組合。可以使用 std::sort 先將輸入的數字排序，然後使用 std::next_permutation 產生下一個排列組合，直到沒有新的排列組合為止。next_permutation 函數會直接修改輸入的序列，並返回一個布林值，表示是否成功產生了下一個排列組合。
複雜度分析
- 時間複雜度: O(N! * N)
- 空間複雜度: O(N)
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int n;
cin >> n;
long long int a[n];
for(int i=0;i<n;++i)
cin >> a[i];
sort(a,a+n);
do{
for(int i=0;i<n;++i)
cout << a[i] << " ";
cout << "\n";
}while(next_permutation(a,a+n));
}