题目描述

原题链接：46. 全排列

解题思路

本题是排列问题与组合问题区别在于，排列问题是区分元素顺序的，同一个元素占据不同的位置，代表不一样的结果。而组合问题不区分元素顺序，同一个元素，只要在这个结果中无论占据那个位置都认为相同的。即数组1, 2的排列可以有1, 2和2, 1作为两个不同的结果，而组合对于1, 2和2, 1认为是通过一种结果。

此题是排列的一般性问题，数组中无重复元素，不允许单个结果内有重复元素，但要求获取按不同顺序获取的数。设置一个vector<bool> visited来判定元素之前是否访问过，若访问过则访问其余元素。

class Solution {
public:    
    vector<int> path;
    vector<vector<int>> res;
    void backtracking(vector<int> nums, vector<bool> visited) {
        if(path.size() == nums.size()) {
            res.push_back(path);
            return ;
        }
        for(int i = 0; i < nums.size(); i++) {
            if(visited[i] == false) {
                visited[i] = true;
                path.push_back(nums[i]);
                backtracking(nums, visited);
                path.pop_back();
                visited[i] = false;
            }            
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<bool> visited(nums.size(), false);
        backtracking(nums, visited);
        return res;
    }
};

参考文章：46. 全排列