Permutations

Given a collection of distinct integers, return all possible permutations.

Example:

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

Algorithm:

1 In Permutation, order of elements matter. Given a list of n integers that are distinct, in order to generate all their permutations, we go about adding the given order of elements first as one valid permutation. Thereafter we swap n-1 and n-2 elements (the right half), while keeping 0th to n-3 fixed (the left half) and arrive at another valid permutation combination. Progressively keep expanding the right half towards the left for further rearrangement among themselves while shrinking the number of fixed elements in the left half. This way we would have generated all permutations possible keeping i = 0th element fixed when we back track the right half towards the 0th element. Backtracking further by removing the first element and then keeping the subsequent next element fixed and rearranging the rest, we will eventually obtain all permutations possible for the given n distinct elements (n! permutations possible).

2 To each backtracking recursive function call, we pass in the res result list of lists, the input nums array, and the tempList and tempSet, the former to curate the permutation list to be added to the res, and the latter, for faster contains method call ( O(1) as compared to list contains O (n)) to ensure that each new element added to form permutation is unique and thereby results in a new arrangement.

3 Whenever tempList size equals nums length, we add the curated tempList to the resultant list of lists res and return to the calling recursive function. Otherwise we iterate through the nums array, and skip continue the current iteration if the current element is already contained in the tempSet, else adding the current element to both the tempList and tempSize, and making a subsequent backtracking recursive function call. Once our backtracking function call gets returned back, we remove the last element from both the tempSet and tempList so as to examine a new permutation rearrangement.

Test:

1 Test with empty or null input array.

2 Test with sorted and unsorted input array.

3 Test with a single element, as well as very large number of elements.

Solution:

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        
        //declare result list of lists to be returned
        List<List<Integer>> res = new ArrayList<>();
        
        if (nums == null || nums.length == 0) {
            return res;
        }
        
        backtrack(nums, res, new ArrayList<Integer>(), new HashSet<Integer>());
        
        return res;
        
    }
    
    private void backtrack(int[] nums, List<List<Integer>> res, List<Integer> tempList, Set<Integer> tempSet) {
        
        if (tempList.size() == nums.length) {
            res.add(new ArrayList<Integer>(new ArrayList<Integer>(tempList)));
            return;
        }
        
        for (int i = 0; i < nums.length; i++) {
            if (tempSet.contains(nums[i])) {
                continue;
            }
            
            tempSet.add(nums[i]);
            tempList.add(nums[i]);
            
            backtrack(nums, res, tempList, tempSet);
            
            tempSet.remove(tempList.get(tempList.size() - 1));
            tempList.remove(tempList.size() - 1);
        }
    }
    
    //T O(n!) S O(n)
}

//https://gist.github.com/harycane/4681dd19910abeb1dfbab31b9330a739

Complexity Analysis:

Since there are n! permutations possible for n distinct elements, therefore the time complexity for our backtracking algorithm is given by the upper bound of T O(n!). Space complexity by virtue of having tempList and tempSet of size n, would be S O(n).