给定一个没有重复数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
解
使用回溯算法，问题可以转化为生成一棵树，树的每一个路径都是一个有效的排列，为了防止出现重复的数字，使用一个used数组记录数字是否已经访问，记录完之后，需要弹出该数字并标记为未访问。
public static List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
int len = nums.length;
boolean[] used = new boolean[len];
if(0==len)
return res;
generatePermution(nums,used,0,len,new Stack<>(),res);
return res;
}
public static void generatePermution(int []nums,boolean[] used,int current,int len,Stack<Integer> path,List<List<Integer>> res) {
if(current == len) {
//找到一个排列
res.add(new ArrayList<>(path));
return;
}
for(int i = 0;i<len;i++) {
if(!used[i]) {
path.push(nums[i]);
used[i] = true;
generatePermution(nums,used,current+1,len,path,res);
//返回上一个节点 记得标记为未访问
path.pop();
used[i] = false;
}
}
}
