1. Answer key

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;
}