current position:Home>46. Full arrangement (c + + problem solution, including vs runnable source program)

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

2022-01-27 04:37:40 Bufan

46. Full Permutation (C++ Problem solution contains VS Can run the source program )

1. Answer key

backtracking

  • Using backtracking algorithm , Depth-first traversal + Status reset
     Insert picture description here

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

copyright notice
author[Bufan],Please bring the original link to reprint, thank you.
https://en.cdmana.com/2022/01/202201270437348767.html

Random recommended