题解分享
题解分享简介
全排列 - 题解
```
#include
using namespace std;
int main(){
int n;
cin>>n;
int a[1010];
for(int i=1; i<=n; i++){
a[i]=i;
}
do{
for(int i=1; i<n; i++){
printf("%d ",a[i]);
}
printf("%d\n",a[n]);
}while(next_permutation(a+1,a+n+1));//直接用内置的全排列函数写就行了，注意先输出已有的第一中排列，所以要用do-while
return 0;
}
```
查看全文
0
0
1
4
全排列 - 题解
```
/*
#include <iostream>
#include <vector>
using namespace std;
// 递归函数，用于生成全排列
void permute(vector<int>& nums, size_t start, vector<vector<int>>& result) {
if (start == nums.size() - 1) { //递归终止条件
result.push_back(nums); // 将当前排列加入结果
} else {
for (size_t i = start; i < nums.size(); i++) { //从start位置开始遍历
//核心代码 ===》靠近终止条件 ==》 start+1 代表上一个位置被固定
//那start == nums.size() - 1 代表已经到最终位置了
swap(nums[start], nums[i]); // 交换元素使得每一个元素都在start位置试试
permute(nums, start + 1, result); // 递归生成排列
swap(nums[start], nums[i]); // 恢复原状
}
}
}
int main() {
int n;
cin >> n;
vector<int> nums(n);
for (int i = 0; i < n; i++) {
nums[i] = i + 1; // 初始化数组
}
vector<vector<int>> result; // 存储所有排列
permute(nums, 0, result); // 生成全排列
// 输出所有排列
for (const vector<int>& perm : result) {
for (int num : perm) {
cout << num << " ";
}
cout << endl;
}
for ( size_t i = 0; i < result.size(); i++ ) {
for ( size_t j = 0; j < result[i].size(); j++ ) {
cout << result[i][j] << " ";
}
if(i != result.size() - 1)
cout << endl;
}
return 0;
}
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> nums(n);
for (int i = 0; i < n; i++) {
nums[i] = i + 1; // 初始化数组
}
// 使用 std::next_permutation 生成所有排列
//next_permutation 的作用是将一个序列（如数组或向量）重新排列，使其成为字典序中的下一个排列。
//如果当前序列已经是字典序中的最大排列（例如 321），那么它会将序列重置为最小排列（例如 123）。
do {
for (int num : nums) {
cout << num << " ";
}
cout << endl;
} while (next_permutation(nums.begin(), nums.end()));
return 0;
}
```
查看全文
0
0
0
5
全排列 - 题解
提供两种解法：
next_permutation
```
#include <bits/stdc++.h>
using namespace std;
const int N = 20;
int a[N];
int n;
int main(){
scanf("%d",&n);
for (int i = 1; i <= n; ++i) {
a[i] = i;
}
do{
for (int i = 1; i <= n; ++i) {
printf("%d ",a[i]);
}
printf("\n");
}while(next_permutation(a + 1,a + n + 1));
return 0;
}
```
DFS
```
#include <bits/stdc++.h>
using namespace std;
const int N = 20;
int vis[N];
int a[N];
int n;
void dfs(int x){
if (x > n) {
for (int i = 1; i <= n; ++i) {
printf("%d ",a[i]);
}
printf("\n");
}
for (int i = 1; i <= n; ++i) {
if(!vis[i]) {
vis[i] = 1;
a[x] = i;
dfs(x + 1);
a[x] = 0;
vis[i] = 0;
}
}
}
int main(){
scanf("%d",&n);
dfs(1);
return 0;
}
```
查看全文
0
0
0
6
全排列 - 题解
```cpp
// https://dashoj.com/p/82
#include <bits/stdc++.h>
using namespace std;
const int N = 15;
int n, cnt = 0;
bool nb[N];
vector<int> cl;
void out() {
for (int i = 0; i < cl.size(); i++) {
cout << cl[i] << ' ';
}
cout << endl;
}
void dfs(int x, int c) {
if (cl.size() == n) {
out();
return;
}
for (int i = 1; i <= n; i++) {
if (nb[i]) {
nb[i] = false;
cl.push_back(i);
dfs(i, c + 1);
cl.pop_back();
nb[i] = true;
}
}
}
int main() {
fill(&nb[0], &nb[0] + N, true);
cin >> n;
for (int i = 1; i <= n; i++) {
nb[i] = false;
cl.push_back(i);
dfs(i, 1);
cl.pop_back();
nb[i] = true;
}
return 0;
}
```
查看全文
0
0
0
2
全排列 - 题解
include
using namespace std;
int num[10],str[10];
int ans=0;
void dfs(int n,int n2){
for(int i=1;i
>n2;
dfs(1,n2);
return 0;
}
查看全文
0
0
0
4
全排列 - 题解
```
#include<bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> v;
for(int i=1;i<=n;i++){
v.push_back(i);
}
do{
for(int num :v){
cout << num << " ";
}
cout << endl;
}while(next_permutation(v.begin(),v.end()));
}
```
查看全文
0
0
0
1
全排列 - 题解
```
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
int a[1000];
for (int i = 0; i < n; i++) {
a[i] = i + 1;
}
do {
for (int i = 0; i < n; i++) {
cout << a[i];
if (i != n - 1) {
cout << " ";
}
}
cout << endl;
} while (next_permutation(a, a + n));
return 0;
}
```
查看全文
0
0
0
1
全排列 - 题解
```
n = int(input())
nums = [i for i in range(1,n+1)]
res = []
path = []
used = [0]*n
def dfs(nums,path,used,n):
if len(path) == n:
print(*path)
for i in range(n):
if used[i]:
continue
used[i] = 1
path.append(nums[i])
dfs(nums,path,used,n)
path.pop()
used[i] = 0
dfs(nums,path,used,n)
```
查看全文
0
0
0
2
全排列 - 题解
include
using namespace std;
int a[20], x, n;
int b[20];
void dfs(int x) {
if (x > n) {
for (int i = 1; i
> n;
dfs(1);
return 0;
}
查看全文
0
0
0
2
全排列 - 题解
```
#include <bits/stdc++.h>
using namespace std;
int n = 0;
vector<int> v;
int main(){
cin >> n;
for(int i = 1 ; i <= n ; i++){
v.push_back(i);
}
do{
for(int i = 0 ; i <n ; i++){
cout << v[i] << " ";
}
cout << endl;
} while(next_permutation(v.begin(), v.end()));
return 0;
}
```
查看全文
0
0
0
1
