给定一个 没有重复 数字的序列，返回其所有可能的全排列。
输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
回溯解法一：逐一尝试
class Solution { public List<List<Integer>> permute(int[] nums) { int[] visited = new int[nums.length]; ArrayList<List<Integer>> result = new ArrayList<>(); ArrayList<Integer> tmp = new ArrayList<>(); backtrack(result, tmp, nums, visited); return result; } public void backtrack(ArrayList<List<Integer>> result, ArrayList<Integer> tmp, int[] nums, int[] visited) { if(tmp.size() == nums.length) result.add(new ArrayList<>(tmp)); for(int i = 0; i < nums.length; i++){ if (visited[i] == 1) continue; tmp.add(nums[i]); visited[i] = 1; backtrack(result, tmp, nums, visited); tmp.remove(tmp.size()-1); visited[i] = 0; } } }回溯解法二：交换
class Solution { public List<List<Integer>> permute(int[] nums) { ArrayList<List<Integer>> result = new ArrayList<>(); ArrayList<Integer> tmp= new ArrayList<>(); for(int num : nums) tmp.add(num); backtrack(nums.length, 0, result, tmp); return result; } public void backtrack(int m, int n, ArrayList<List<Integer>> result, ArrayList<Integer> tmp) { if(n == m) result.add(new ArrayList<>(tmp)); for(int i = n; i < m; i++) { Collections.swap(tmp, n, i);//做选择 backtrack(m, n+1, result, tmp); Collections.swap(tmp, n, i);//撤销选择 } } }重复数字剪枝：（添加代码）
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) { continue; }