Permutations

全排列

题目

Given a collection of distinct integers, return all possible permutations.

Example:

Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

解析重点

1.这本质上一道数学题，只是需要用代码合适的表示出来。全排列的话，等于数据个数的阶层n！。那么我们可以用递归来实现，
第一层递归循环数组所有的数，第二层循环n-1个数，一直到最后一层，这样就把所有的都找出来了。
2.但是，这么做会产生很多小对象，所以改为每层递归都循环所有的数n，然后如果零时数组包含的相关数，则跳出此次循环，这
样就不会出现重复的。
3.可以把原始数组转换成hashMap的结构，这样检查临时数组是否包含相关数时可以减少复杂度。

java代码

原始数组转换成hashMap的结构就交给大家了，我这里没写。。。

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        recPermute(list,nums,new ArrayList<>());
        return list;
    }

    public void recPermute(List<List<Integer>> list,int[] nums,List<Integer> tempList){
        if(tempList.size() == nums.length){
            list.add(new ArrayList<>(tempList));
        }else{
            for(int i = 0; i < nums.length; i++){
                if(tempList.contains(nums[i])) continue; // element already exists, skip
                tempList.add(nums[i]);
                recPermute(list, nums, tempList);
                tempList.remove(tempList.size() - 1);
            }
        } 
    }
}