算法题每日一练：全排列

输入： 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]]

1.回溯算法2.建议用时20~35min

    vector<int>t;    int visit[10]={0};//判断元素是否被存储    vector<vector<int>>v;void DFS(int n,vector<int>& nums)//函数初始

if(t.size()==n)//终止条件{    v.push_back(t);    return;}

for(int i=0;i<n;i++)//递归处理{   if(!visit[i])//是否被访问    {       visit[i]=1;//标记为1，存入数组       t.push_back(nums[i]);       DFS(nums.size(),nums);       visit[i]=0;//回溯       t.pop_back();    }}

递归之前 => [1] 递归之前 => [1, 2] 递归之前 => [1, 2, 3] 递归之后 => [1, 2] 递归之后 => [1] 递归之前 => [1, 3] 递归之前 => [1, 3, 2] 递归之后 => [1, 3] 递归之后 => [1] 递归之后 => [] 递归之前 => [2] 递归之前 => [2, 1] 递归之前 => [2, 1, 3] 递归之后 => [2, 1] 递归之后 => [2] 递归之前 => [2, 3] 递归之前 => [2, 3, 1] 递归之后 => [2, 3] 递归之后 => [2] 递归之后 => [] 递归之前 => [3] 递归之前 => [3, 1] 递归之前 => [3, 1, 2] 递归之后 => [3, 1] 递归之后 => [3] 递归之前 => [3, 2] 递归之前 => [3, 2, 1] 递归之后 => [3, 2] 递归之后 => [3] 递归之后 => [] 输出 => [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

void DFS(变量)//函数初始{    if(条件1||条件2...)//终止条件    {         v.push_back(t);         return;    }    if (条件1||条件2...)//剪枝         return;    for(int i=cur;i<=n;i++)//递归处理    {        //选择当前数字        DFS(向下遍历);        //回退    } }

class Solution {public:    vector<int>t;    int visit[10]={0};//判断元素是否被存储    vector<vector<int>>v;    void DFS(int n,vector<int>& nums)//函数初始    {        if(t.size()==n)//终止条件        {            v.push_back(t);            return;        }        for(int i=0;i<n;i++)//递归处理        {            if(!visit[i])//是否被访问            {                visit[i]=1;//标记为1，存入数组                t.push_back(nums[i]);                DFS(nums.size(),nums);                visit[i]=0;//回溯                t.pop_back();            }        }    }    vector<vector<int>> permute(vector<int>& nums) {        DFS(nums.size(),nums);//传入数据        return v;    }};