Permutations I

/*
Backtracking (Using TempList approach)

Time Complexity : O(n * (n!))
Number of Permutations = n P n = n!
Time taken to create each permutation = O(n)

Space Complexity = O(n) -> Max depth of the tree + size of the visited array.
*/
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums == null) {
            return result;
        }
        if (nums.length == 0) {
            result.add(new ArrayList<Integer>());
            return result;
        }

        boolean[] visited = new boolean[nums.length];

        backtrack(result, new ArrayList<Integer>(), nums, visited);
        return result;
    }

    public void backtrack(List<List<Integer>> list, ArrayList<Integer> tempList, int[] nums, boolean[] visited) {
        if (tempList.size() == nums.length) {
            list.add(new ArrayList<>(tempList));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (visited[i] == true) {
                continue;
            }
            visited[i] = true;
            tempList.add(nums[i]);
            backtrack(list, tempList, nums, visited);
            visited[i] = false;
            tempList.remove(tempList.size() - 1);
        }
    }
}

/*
Backtracking (Swapping apporach)

Time Complexity : O(n * (n!))
Number of Permutations = n P n = n!
Time taken to create each permutation = O(n)

Space Complexity = O(n) -> Max depth of the tree
*/
// class Solution {
//     public List<List<Integer>> permute(int[] nums) {
//         List<List<Integer>> result = new ArrayList<>();
//         if (nums == null) {
//             return result;
//         }
//         if (nums.length == 0) {
//             result.add(new ArrayList<Integer>());
//             return result;
//         }

//         backtrack(result, nums, 0);
//         return result;
//     }

//     public void backtrack(List<List<Integer>> list, int[] nums, int start) {
//         if (start == nums.length) {
//             List<Integer> tempList = new ArrayList<>();
//             for (int num : nums) {
//                 tempList.add(num);
//             }
//             list.add(tempList);
//             return;
//         }
//         for (int i = start; i < nums.length; i++) {
//             swap(nums, i, start);
//             backtrack(list, nums, start+1);
//             swap(nums, i, start);
//         }
//     }

//     public void swap(int[] nums, int i, int j) {
//         int temp = nums[i];
//         nums[i] = nums[j];
//         nums[j] = temp;
//     }
// }