[46]全排列

//给定一个 没有重复 数字的序列，返回其所有可能的全排列。 
//
// 示例: 
//
// 输入: [1,2,3]
//输出:
//[
//  [1,2,3],
//  [1,3,2],
//  [2,1,3],
//  [2,3,1],
//  [3,1,2],
//  [3,2,1]
//] 
// Related Topics 回溯算法 
// 👍 1142 👎 0

/*
* 46 全排列
* 2021-02-22 16:18:01
* @author oxygenbytes
*/ 
#include "leetcode.h" 
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public:
    vector<vector<int>> ans;
    vector<int> cur;
    vector<vector<int>> permute(vector<int>& nums) {
        int n = nums.size();
        vector<bool> vis(n + 1, false);
        dfs(n, nums, vis);
        return ans;
    }

    void dfs(int n, vector<int>& nums, vector<bool>& vis){
        if(cur.size() == n){
            ans.push_back(cur);
            return ;
        }

        for(int i = 1;i <= n;i++){
            if(!vis[i]){
                cur.push_back(nums[i-1]);
                vis[i] = true;
                dfs(n, nums, vis);
                vis[i] = false;
                cur.pop_back();
            }
        }
    }
};
//leetcode submit region end(Prohibit modification and deletion)