King Of Interviews

Permutations: Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Example 1:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2:

Input: nums = [0,1]
Output: [[0,1],[1,0]]

Example 3:

Input: nums = [1]
Output: [[1]]

Constraints:

1 <= nums.length <= 6
-10 <= nums[i] <= 10
All the integers of nums are unique.

Try this Problem on your own or check similar problems:

Solution:

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        helper(nums, new ArrayList<>(), result, new HashSet<>());
        return result;
    }

    private void helper(int[] nums, List<Integer> currentList, List<List<Integer>> result, Set<Integer> visited){
        if(currentList.size() == nums.length){
            result.add(new ArrayList<>(currentList));
            return;
        }
        for(int i = 0; i < nums.length; ++i){
            if(!visited.contains(nums[i])){
                currentList.add(nums[i]);
                visited.add(nums[i]);

                helper(nums, currentList, result, visited);

                currentList.remove(currentList.size() - 1);
                visited.remove(nums[i]);

            }
        }
    }
}

Time/Space Complexity:

Time Complexity: O(n*n!)
Space Complexity: O(n)

Explanation:

Notice that the solution look similar to the Subsets , but there are two important difference:

order is important in permutations (1,2,3) != (1,3,2) (if they were subsets they would be equal)
each permutation length is equal to the input array length, in other words we have to select all elements in the input array.

So, we can use these two differences to model our solutions. We only add the currentList if its current length is equal to that of the input array. Next, since any element in the input array can be placed at any index and each time it’s placed at another index we get a new permutation, we must position each element at every possible index in array and try to generate a new permutation. How do we know that element is already chosen? Well, we utilize the visited set which when queried give us information if the element has already been selected (added to the currentList). If it wasn’t selected, we place it in the next position in currentList, add it to the visited set and go deeper in the recursion. But we also must backtrack so after the recursion call, we remove the element from both visited and currentList. The time complexity for permutations is O(n!), but we also have a multiplier of n because of list copying. For space complexity since we’re only building the list with size equal to the input array, we have linear space complexity O(n).

Permutations