class Solution {
    
    List<List<Integer>> list = new ArrayList<>();
    List<Integer> temp = new LinkedList<>();
    
    // 순열: Backtracking
    // Time complexity : O(n!)
    public List<List<Integer>> permute(int[] nums) {
       backtrack(nums, 0);
        
       return list;
    }

    private void backtrack(int[] nums, int i) {
    
        if (i == nums.length) {
            list.add(new ArrayList(temp));
            return;
        }

        //Insert elements in the array by increasing index
        for (int j = 0; j <= i; j++) {
            temp.add(j, nums[i]);
            backtrack(nums, i + 1);
            temp.remove(j);
        }
    }
}