# 46. Full arrangement (c + + problem solution, including vs runnable source program)

2022-01-27 04:37:40 Bufan

## backtracking

• Using backtracking algorithm , Depth-first traversal + Status reset • If all arranged , The candidate interval of the current node value is ： Unused in the path from the root to the current node , So you need to use used The array marks the value used by this path .

• Naturally, the selection of the current node value is from 0 Start , All unmarked ones can , If you make a choice , Just add this to the path used in , The next level of recursion will not be repeatedly selected .

• And for the nodes behind the same layer , The site needs to be restored , Restore the selected one to false, This will not affect the children behind the node .

The problem of permutation ：

1. The problem of permutation ：for Cycle from 0 Start , need continue Is the value used in the path from the root to the current node （ use used Mark ）
2. The termination condition of the permutation problem is path Reach the leaf node

# 2. Power button C++ Source code

``````class Solution {

public:
vector<vector<int>> permute(vector<int>& nums) {

vector<bool> used(nums.size(), false);
backtracking(nums, used);

return res;
}
vector<vector<int>> res;
vector<int> path;
void backtracking(vector<int>& nums, vector<bool>& used) {

if (nums.size() == path.size()) {

res.push_back(path);
//return;
}
for (int i = 0; i < nums.size(); i++) {

if (used[i] == true)continue;
used[i] = true;
path.push_back(nums[i]);
backtracking(nums, used);
path.pop_back();
used[i] = false;
}
}
};
``````

# 3.VS Can run the source program

``````#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<limits>
#include<algorithm>
#include<math.h>
#pragma warning(disable:4996)
using namespace std;

// to flash back , Depth-first traversal + Status reset
class Solution {

public:
vector<vector<int>> permute(vector<int>& nums) {

//used Marked is the path from the root to any node , Used value
vector<bool> used(nums.size(), false);
backtracking(nums, used);

return res;
}
vector<vector<int>> res;
vector<int> path;
void backtracking(vector<int>& nums, vector<bool>& used) {

if (nums.size() == path.size()) {

res.push_back(path);
//return;
}
for (int i = 0; i < nums.size(); i++) {

// For the termination condition of the arrangement , yes path To the leaf node
if (used[i] == true)continue;
used[i] = true;
path.push_back(nums[i]);
backtracking(nums, used);
path.pop_back();
// Restore the scene , This step is to avoid affecting the children of the nodes behind the current layer
used[i] = false;
}
}
};
int main()
{

printf(" Enter the number of array elements ：");
int n;
scanf("%d", &n);
printf(" Input array elements ：");
int num;
vector<int> nums;
for (int i = 0; i < n; i++) {

scanf("%d", &num);
nums.push_back(num);
}
Solution test;
vector<vector<int>> res = test.permute(nums);
printf(" The full array sequence of array elements is ：");
for (int i = 0; i < res.size(); i++) {

for (int j = 0; j < res[i].size(); j++) {

printf("%d ", res[i][j]);
}
printf("\n");
}

printf("\n");
system("pause");
return 0;
}
``````