题目内容

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

示例

示例 1：

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

示例 2：

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

示例 3：

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

提示

1、1 <= nums.length <= 6
2、-10 <= nums[i] <= 10
3、nums 中的所有整数 互不相同

题解

本题可以使用深度优先搜索算法求解。

首先，从前往后，一位一位枚举，每次选择一个没有被使用过的数。
然后，将该数的状态改成“已被使用”，同时将该数记录在相应位置上，然后递归。

注意：递归返回时，需要将该数的状态改成“未被使用”，并将该数从相应位置上删除。因为在某一条路径（dfs）走到底往回走的时候，要把走过的印记擦除掉，如果不擦除的话，那么整个dfs就只会返回一条路径，从一个点往不同分支走的时候要保证不同分支相互之间没有影响才行，所以从每个分支退回来的时候需要把修改过的状态还原。

具体，请看代码实现。

代码

class Solution {
public:

    vector<vector<int>> ans;//全局结果
    vector<int> path;//路径
    vector<bool> st;//标志位，用于记录数字是否被使用

    vector<vector<int>> permute(vector<int>& nums) {
        path = vector<int>(nums.size());//初始化path
        st = vector<bool>(nums.size());//初始化st

        dfs(nums,0);//传递当前第几位
        return ans;
    }
		//实现搜索算法，u代表当前枚举第几位
    void dfs(vector<int>& nums, int u){
        if(u == nums.size()){
          	//如果u枚举到了最后一位，则说明搜索完毕，将答案记录到全局结果中，然后返回
            ans.push_back(path);
            return;
        }
      	//递归遍历求解
        for(int i = 0; i < nums.size(); i++){
            if(st[i] == false){
              	//当某个数没有被使用时，当前位置采用该数，并将该数的标志修改为true，表示已经使用过，然后递归下一位。
                path[u] = nums[i];
                st[i] = true;
                dfs(nums,u + 1);
                st[i] = false;//要注意恢复现场，具体解释见题解中的注意事项
            }
        }
    }
};