Java: Permutations

Thought Process

To generate all permutations of a given array, we use backtracking. We start by building permutations one element at a time. If the current element is already in the temporary permutation, we skip it. Otherwise, we add it to the permutation and recursively continue the process. This ensures that we generate all possible permutations of the array. 

class Solution {

    public void backTrack(List<List<Integer>> ans, List<Integer> tmp, int[] nums){

        if(tmp.size()==nums.length){
            ans.add(new ArrayList<>(tmp));
            return;
        }

        for(int i=0;i<nums.length;i++){
            // If Element already exist in our set, then skip it.
            if(tmp.contains(nums[i]))
                continue;

            tmp.add(nums[i]);
            backTrack(ans,tmp,nums);
            tmp.remove(tmp.size()-1);
        }
    }
    public List<List<Integer>> permute(int[] nums) {
        
        List<List<Integer>>  ans = new ArrayList<>();
        List<Integer> tmp = new ArrayList<>();

        backTrack(ans,tmp,nums);

        return ans;
    }
}

Code Complexity

Time Complexity: O(n * n!)

The algorithm generates all permutations of the input array, resulting in n! permutations, and each permutation takes O(n) time to construct, where 'n' is the size of the input.

Space Complexity: O(n)

The recursion stack depth is proportional to the size of the input('n'), and the temporary list stores intermediate results.

Code copied!