46. 全排列

给定一个没有重复数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]

输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

Solution：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        int len = nums.size();
        vector<bool> isVisit(len,false);
        vector<vector<int>> res;
        vector<int> temp;
        DFS(nums,isVisit,res,temp);
        return res;
        
    }
    void DFS(vector<int> & nums, vector<bool> &isVisit, vector<vector<int>> &res, vector<int> &temp){
        if(temp.size() == nums.size()){
            res.push_back(temp);
            return;
        }
        for(int i = 0; i < nums.size(); i++){
            if(isVisit[i]) continue;
            temp.push_back(nums[i]);
            isVisit[i] = true;
            DFS(nums,isVisit,res,temp);
            temp.pop_back();
            isVisit[i] = false;
        }
    }
};

思路：

对于每一个数在一个排列中出现且仅出现一次。所以需要定义一个记录该数是否访问过的与原数组相同长度的数组——isVisit。

首先限定递归层数，当temp数组的长度已经和原数组的长度相同，就将数组保存下来。

然后开始遍历数组中的每一个数，遇到一个数，就将该数标记为已访问，并且将该数添加到temp数组中。继续下一层递归。

回溯：

当每一个数访问完后，将该数从temp中pop掉，然后接着探寻下一个数是不是符合条件。