leetcode16

解题思路

思路主要是DP，但看题解的回溯好像和我的DP也有异曲同工之妙 DP主要是找转移方程，由于这题很明显的有最优子结构：即长度为n的全排列包含长度为n-1的全排列（只要把长度为n的全排列去掉第n个数然后去重就好了） 转移方程即为：长度为n的nums[]的全排列=长度为n-1的子数列在每个可能的位置插入nums[n] 实际上插入的过程分为两步，第一步是将子数列的全排列数组扩容，第二步才是插入

代码

class Solution {
   public List<List<Integer>> permute(int[] nums) {
//用来存答案的数组
        List<List<Integer>> ans = new ArrayList<>();
//首先判断特例
        if(nums.length<1)
            return null;
//开始自底而上DP
        for (int i : nums
        ) {
//用来存单个的排列
            List<Integer> temp;
//用来保存下一层的答案
            List<List<Integer>> ttt = new ArrayList<>();
//遍历上一层全排列，然后对每一种排列都进行size+1次的插入操作（因为长度为n的数组有n+1个插入位置）
            for (List<Integer> t : ans
            ) {
                int len=t.size();
                for (int j = 0; j < len+1 ; j++) {
//这里才初始化是因为不然循环时会保留信息
                    temp=new ArrayList<>();
                    temp.addAll(t);
//将i插入位置j
                    temp.add(j,i);
//下一层储存答案
                    ttt.add(temp);
             }
            }
//这是第一个数插入时的特殊情况
            if (ans.isEmpty()) {
                temp=new ArrayList<>();
                temp.add(i);
                ans.add(temp);
            }
//更新ans成下一层的答案再进入循环
            else {
                ans=ttt;
            }
        }
        return ans;
    }
}