题解 | #没有重复项数字的全排列#

using System;
using System.Collections.Generic;


class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num int整型一维数组 
     * @return int整型二维数组
     */
    public bool[] flag;
    public List<List<int>> ans=new List<List<int>>();
    public List<List<int>> permute (List<int> num) {
        // write code here
        flag=new bool[num.Count];
        dfs(num, new List<int>());
        return ans;
        
    }
    public void dfs(List<int> num, List<int> vec)
    {
        if(vec.Count==num.Count)
        {
            ans.Add(new List<int>(vec));
            return;
        }
        for(int i=0;i<num.Count;i++)
        {
            if(flag[i])
                continue;
            vec.Add(num[i]);
            flag[i]=true;
            dfs(num, vec);
            vec.RemoveAt(vec.Count-1);
            flag[i]=false;
        }
    }
}

深度优先，回溯法。不大理解的可以用 1 2 3画个树形图。
1.需要一个等长的bool数组来标记已经访问的
2.新添加一个元素后，需要撤回