Permutation

Solution.java

// https://leetcode.com/problems/permutations/
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ans = new ArrayList();
        if(nums == null || nums.length == 0) return ans;
        
        ans.add(new ArrayList());
        
        for(int i = 0; i < nums.length; i++) {
            int size = ans.size();
            int num = nums[i];
            
            for(int j = 0 ; j < size; j++) {
                // poll first from ans
                List<Integer> list = ans.get(0);
                // loop through it
                for(int k = 0; k <= list.size(); k++) {
                    // clone it
                    List<Integer> clonedList = new ArrayList(list);
                    
                    if(k < list.size()) {
                        // add num in each one of them in each index
                        clonedList.add(k, num);
                    } else {
                        // add num in each one of them in each index (at to last)
                        clonedList.add(num);
                    }
                    // add cloned list
                    ans.add(clonedList);
            }
                // remove the original list
                ans.remove(0);
            }        
        }
        
        return ans;
    }
}
// 1,2,3
// pre-add empty list
// []

// poll lists from ans
// clone it
// add num in each one of them in each index
// remove the original list
// [1]

// poll lists from ans
// clone it
// add num in each one of them in each index
// remove the original list
// [1,2] [2, 1]

// poll lists from ans
// clone it
// add num in each one of them in each index
// remove the original list
// [3,1,2] [3, 2, 1] [1,3, 2] [2,3, 1] [1,2, 3] [2, 1, 3]

Outer loop = O(n)
2 inner loops = O(n!) since it is a permutation. E.g. [1,2,3,4] has 24 permutations [123*4]

Time = O(n * n!)