扬中网站建设开发网络营销案例分析及答案

我在网上看的博客大部分是告诉你这是卡特兰数，然后只给出了如何求解有多少种排列，没有给出具体排列是怎么样的。如果你还不知道卡特兰数，请查看：https://leetcode.cn/circle/discuss/lWYCzv/

这里记录一下如何生成每种具体的排列：（c++实现）

// 回溯#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>using namespace std;void backtrack(vector<int>& nums, vector<int>& permutation, vector<bool>& used, vector<vector<int>>& result) {if (permutation.size() == nums.size()) {result.push_back(permutation);return;}for (int i = 0; i < nums.size(); i++) {if (!used[i]) {used[i] = true;permutation.push_back(nums[i]);backtrack(nums, permutation, used, result);permutation.pop_back();used[i] = false;}}
}vector<vector<int>> findPermutations(vector<int>& nums) {vector<vector<int>> result;vector<int> permutation;vector<bool> used(nums.size(), false);backtrack(nums, permutation, used, result);return result;
}int main() {int n;cin >> n;vector<int> nums(n);for (int i = 0; i < n; i++) {cin >> nums[i];}vector<vector<int>> permutations = findPermutations(nums);printf("出栈顺序有%d种: \n", permutations.size());for (const auto& permutation : permutations) {for (int num : permutation) {cout << num << " ";}cout << endl;}return 0;
}