46.全排列

方法：回溯法

一種通過探索所有可能的候選解來找出所有的解的算法，如果候選解被確認不是一個解，回溯法會通過在上一步進行一些變化拋棄該解，即回溯并且再次嘗試

使用一個標記數組表示已經填過的數

class Solution {public List<List<Integer>> permute(int[] nums) {List<List<Integer>> res = new ArrayList<List<Integer>>();List<Integer> output = new ArrayList<Integer>();int n = nums.length;boolean[] visited = new boolean[n];backtrack(res,output,visited,nums);return res;}public void backtrack(List<List<Integer>> res,List<Integer> output,boolean[] visited,int[] nums){if(output.size() == nums.length){res.add(new ArrayList(output));return;}for(int i = 0;i<nums.length;i++){if(!visited[i]){output.add(nums[i]);visited[i]=true;backtrack(res,output,visited,nums);//退到上一狀態visited[i]=false;output.remove(output.size()-1);}}}}