题目描述

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

样例

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

输入：nums = [0,1]
输出：[[0,1],[1,0]]

输入：nums = [1]
输出：[[1]]

算法1

dfs爆搜

1、从前往后枚举每一个位置填哪个数
2、如果枚举到nums.size()个位置了，说明已经有一个排列序列了，直接放入答案中。
3、否则从前往后看哪个数没有被放在前面，则可以放在当前位置，同时标记这个数现在被用过了，之后不能用
4、然后递归去枚举下一个位置
5、同时当一个排列序列找到后，会进行回溯，恢复状态，找到上一个分支可以选的另一选择进行dfs

时间复杂度

C++ 代码

class Solution {
public:

    /*
    从前往后枚举每一个位置填哪个数
    如果枚举到nums.size()个位置了，说明已经有一个排列序列了，直接放入答案中。
    否则从前往后看哪个数没有被放在前面，则可以放在当前位置，同时标记这个数现在被用过了，之后不能用
    然后递归去枚举下一个位置
    同时当一个排列序列找到后，会进行回溯，恢复状态，找到上一个分支可以选的另一选择进行dfs
    */

    vector<vector<int>> ans; 
    vector<int> path; // 存储每个结果的序列
    vector<bool> st; // 标记哪些数字已经被选过

    void dfs(vector<int>& nums,int u) // 第u个位置可以如何选择
    {
        if(u==nums.size())   // 递归出口：如果已经枚举到nums.size()，则记录方案
        {
            ans.push_back(path);
            return;
        }

        // 否则，枚举当前位置可以填哪些数(从前往后看每个数，如果当前的数没有用过，则可以用这个数填当前位置)
        for(int i=0;i<nums.size();i++)
        {
            if(st[i]==false) // i这个位置的数没用过
            {
                path[u]=nums[i];  // 当前位置填nums[i]
                st[i]=true; // 同时记录第i个数已经用过了
                dfs(nums,u+1); // 递归下一层
                st[i]=false; // 回溯，恢复现场：还原到递归前的状态，path[]不用改，每次会覆盖
            }
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        path=vector<int>(nums.size()); // 初始化容量
        st=vector<bool>(nums.size());  // 初始化容量

        dfs(nums,0); // 第二个参数表示：枚举到第几位

        return ans;
    }
};