46. Permutations

这个题在《剑指offer》上面讲过

思路：

1.利用递归

2.遍历，每遍历到一个新的数索引为i，就复制i个新的数组，并且把这个新的数插入新复制出来的数组的各个位置上

java:

 1 class Solution {
 2     public List<List<Integer>> permute(int[] nums) {
 3         List<List<Integer>> res = new ArrayList<List<Integer>>();
 4         if(nums.length==0) return res;
 5         List<Integer> l0 = new ArrayList<Integer>();//用于被复制
 6         l0.add(nums[0]);
 7         res.add(l0);
 8         for(int i=1;i<nums.length;i++){
 9             List<List<Integer>> new_res = new ArrayList<List<Integer>>();
10             for(int j=0;j<=i;j++){
11                 for(List<Integer>l:res){
12                     List<Integer> new_l = new ArrayList<Integer>(l);
13                     new_l.add(j, nums[i]);
14                     new_res.add(new_l);
15                 }
16             }
17             res = new_res;
18         }
19         return res;
20     }
21     
22 }

python:

1 class Solution(object):
2     def permute(self, nums):
3         """
4         :type nums: List[int]
5         :rtype: List[List[int]]
6         """
7         return [ [n]+p for i,n in enumerate(nums) for p in self.permute(nums[:i]+nums[i+1:]) ] or [[]]