[LeetCode] Permutations

Problem:

Given a collection of numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

Solution:O(n!)

public class Solution {
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
        ret.add(new ArrayList<Integer>());
        
        for(int i=0;i<num.length;i++){
            ArrayList<ArrayList<Integer>> cur = new  ArrayList<>();
            for(ArrayList<Integer> tmp:ret){
                for(int j=0;j<tmp.size()+1;j++){
                    tmp.add(j,num[i]);
                    cur.add(new ArrayList<>(tmp));
                    tmp.remove(j);
                }
            }
            ret = new ArrayList<>(cur);
        }
        return ret;
    }
}