前言

题目：46. 全排列

参考题解：46.全排列-代码随想录

提交代码

排列相对于leetcode 77 组合，先取后面之后，必须后头再取前面。所以，回溯过程都要从头开始选择那些没有被选择过的元素，来组成新的排列。

下面代码思路和实现，来自上面参考题解。

#include <vector>
#include <iostream>

using namespace std;

class Solution {
public:
    void backTracking(vector<int>& nums, vector<bool>& used, vector<int>& path, vector<vector<int>>& result){
        if(path.size() == nums.size()){
            result.push_back(path);
            return;
        }

        for(int i=0; i<nums.size(); i++){
            if(used[i])
                continue;
            used[i] = true;
            path.push_back(nums[i]);
            backTracking(nums,used,path,result);
            path.pop_back();
            used[i] = false;
        }
        
    }

    vector<vector<int>> permute(vector<int>& nums) {
        vector<bool> used(nums.size(),false);
        vector<int> path;
        vector<vector<int>> result;
        backTracking(nums,used,path,result);
        return result;
    }
};


int main(void){
    vector<int> nums = {1,2,3};
    Solution s;
    vector<vector<int>> result = s.permute(nums);
    for(auto one : result){
        for(auto num : one)
            cout<<num<<" ";
        cout<<endl;
    }
}