原题链接在这里：https://leetcode.com/problems/permutations/
与Combinations相似，都是NP问题可以采用递归加回朔，递归的终止条件与Combinations相同，item.size()满足要求就把item加到res里。
这里采用boolean [] used数组来代表当前数是否被用过。若是被用过就跳过，没有被用过把nums[i]加到item中，然后递归剩下的元素。
当递归结束后，减掉item尾部元素，同时需要维护used数组，把当前位置变回false, 确保进入递归和结束递归时状态相同。
AC Java:
1 public class Solution { 2 public List<List<Integer>> permute(int[] nums) { 3 List<List<Integer>> res = new ArrayList<List<Integer>>(); 4 if(nums == null || nums.length == 0){ 5 return res; 6 } 7 boolean [] used = new boolean[nums.length]; 8 helper(nums,used,new ArrayList<Integer>(), res); 9 return res; 10 } 11 private void helper(int[] nums, boolean [] used, List<Integer> item, List<List<Integer>> res){ 12 if(item.size() == nums.length){ 13 res.add(new ArrayList<Integer>(item)); 14 return; 15 } 16 for(int i = 0; i<nums.length; i++){ 17 if(!used[i]){ 18 used[i] = true; 19 item.add(nums[i]); 20 helper(nums,used,item,res); 21 item.remove(item.size()-1); 22 used[i] = false; 23 } 24 } 25 } 26 }
这道题的迭代方法如下：
与Subsets相似，开始时item先加第一个元素，然后把item加到res里，然后每次添加新的元素，首先把res里的每一个item拿出来，用cur表示。
在cur的所有可能位置加上新的元素nums[i], 然后把它加载回res里。
Note: res原有的item不能保留，所以每次扫描res所有item前新建newRes, 添加完新元素nums[i]的item是要加到newRes中去的，所有可能的item都加完后再把newRes赋值回res去。
AC Java:
1 public class Solution { 2 public List<List<Integer>> permute(int[] nums) { 3 //Iteration 4 List<List<Integer>> res = new ArrayList<List<Integer>>(); 5 if(nums == null || nums.length == 0){ 6 return res; 7 } 8 List<Integer> item = new ArrayList<Integer>(); 9 item.add(nums[0]); 10 res.add(item); 11 for(int i = 1; i<nums.length; i++){ 12 List<List<Integer>> newRes = new ArrayList<List<Integer>>(); 13 for(int j = 0; j<res.size(); j++){ 14 List<Integer> cur = res.get(j); 15 for(int k = 0; k<cur.size()+1; k++){ 16 item = new ArrayList<Integer>(cur); 17 item.add(k,nums[i]); 18 newRes.add(item); 19 } 20 } 21 res = newRes; 22 } 23 return res; 24 } 25 }
原文：http://www.cnblogs.com/Dylan-Java-NYC/p/4842069.html