题解 | #没有重复项数字的所有排列#

题目思路：
这道题目就是很典型的回溯类题目。
回溯其实也是暴力解法，但是又一些题目可以通过剪枝对算法进行优化，这道题目要找出所有的排列，其实还是比较简单的。
算法的思路主要就是：选择与撤销
例如：1开头的有，[1,2,3]，接着3撤销，2撤销，然后选择3，再选择2，就有了[1,3,2]。
整体用一个图来观看整个过程

方法一：递归

import java.util.*;
public class Solution {
    // 存所有排列的集合
    ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        // 存一种排列
        LinkedList<Integer> list = new LinkedList<>();
        // 递归进行
        backTrack(num,list);
        return res;
    }

    public void backTrack(int[] num, LinkedList<Integer> list){
        // 当list中的长度等于数组的长度，则证明此时已经找到一种排列了
        if(list.size() == num.length){
            // add进返回结果集中
            res.add(new ArrayList<>(list));
            return;
        }
        // 遍历num数组
        for(int i = 0; i < num.length; i++){
            // 若当前位置中的数已经添加过了则跳过
            if(list.contains(num[i]))
                continue;
            // 选择该数
            list.add(num[i]);
            // 继续寻找
            backTrack(num,list);
            // 撤销最后一个
            list.removeLast();
        }
    }
}

复杂度分析:
时间复杂度:。n为num数组的长度。
空间复杂度:。返回的结果的空间。

方法二：不递归版
这种方法不使用递归，其实也是一个选择和撤销的过程，只是不使用递归来完成。
通过插入的方式，一次性找到所有的情况。
例如：第一次选择1，接着可以在1前面和后面插入2，则变为 1，2 和 2，1；接着可选择3，3插入到1，2中有三种分别为 3，1，2；1，3，2；1，2，3；然后3插入2，1也有三种。
其实就是找到能插的位置，同一个数可以插在不同的位置，则构成了另外的排列。

public class Solution {
    // 所有的排列结果集
    ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        ArrayList<Integer> list = new ArrayList<>();
        // 先对res中加入一个空的list，给第一次插入制造一个空间。
        res.add(list);
        // 整个循环的次数为num的元素个数
        for(int i = 0; i < num.length; i++){

            ArrayList<ArrayList<Integer>> tmp = new ArrayList<>();
            // 遍历此时的排列结果
            for(ArrayList<Integer> r:res){
                // 根据集合的大小，使用for循环在可插入的位置进行插入
                for(int j = 0; j < r.size()+1; j++){
                    // 在第j个位置插入
                    r.add(j,num[i]);
                    // 此时构成新的排列集合，可能是不完整的排列集合（例如：[1,2];[2,1]这类）
                    ArrayList<Integer> temp = new ArrayList<>(r);
                    // 放进去tmp临时集合中
                    tmp.add(temp);
                    // 将刚插入的数移除掉，为了将同样的这个插入不同的位置
                    r.remove(j);
                }
            }
            // 最后赋给res进行返回
            res = new ArrayList<>(tmp);
        } 
        return res;
    }
}

复杂度分析:
时间复杂度:。n为num数组的长度。
空间复杂度:。返回的结果的空间。