Solution For Permutations

Problem Statement:

The problem asks us to find all possible permutations of a given array of distinct integers. For example, given the input array [1, 2, 3], the output should be:

Approach:

There are multiple ways to solve this problem, but the most common and simplest ones involve recursion or backtracking.

The basic idea is to fix the first element of the array and recursively generate all possible permutations of the remaining elements. Then move to the second element and repeat the same process until all elements have been fixed as the starting element.

Let’s take an example to understand the approach better:

Suppose we have the following input array [1, 2, 3]. We can start by fixing the first element, which can be 1, 2, or 3. Suppose we fix 1 as the first element. Now, we need to find all possible permutations of the remaining elements [2, 3]. To do this, we can again fix the first element as 2 and recursively find all possible permutations of [3]. This will lead to the permutation [1, 2, 3]. Then, we can fix the first element as 3 and recursively find all possible permutations of [2]. This will lead to the permutation [1, 3, 2].

We repeat the same process for the remaining possible starting elements, which are 2 and 3. For the starting element 2, we fix it and recursively find permutations of [1, 3]. This will lead to the permutations [2, 1, 3] and [2, 3, 1]. Similarly, for the starting element 3, we fix it and recursively find permutations of [1, 2], which will lead to the permutations [3, 1, 2] and [3, 2, 1].

So, we need a recursive function that takes the starting element as an argument and generates all possible permutations of the remaining elements. We can use a loop to iterate through all possible starting elements and call the recursive function for each of them. We also need a base case to stop the recursion if we have reached the end of the input array.

Code:

Here’s the Python code to solve the problem using recursion:

“`
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
res = [] self.permuteHelper(nums, [], res)
return res

def permuteHelper(self, nums, curr, res):
    if not nums:
        res.append(curr)
    for i in range(len(nums)):
        self.permuteHelper(nums[:i] + nums[i+1:], curr + [nums[i]], res)

“`

The permute() function takes the input array as an argument and returns the list of all possible permutations. It initializes an empty list to store the permutations and calls the permuteHelper() function, which takes three arguments: the remaining elements (nums), the current permutation (curr), and the list to store all permutations (res).

The permuteHelper() function first checks if there are no remaining elements in nums. If so, it means we have found one possible permutation, so we add the current permutation to res.

If there are remaining elements, we loop through them and recursively call the permuteHelper() function with the remaining elements (nums[:i] + nums[i+1:]), the current permutation with the current element added (curr + [nums[i]]), and res.

The loop ensures that we generate all possible permutations by trying all possible starting elements. The recursive call generates all possible permutations of the remaining elements.

Time Complexity:

The time complexity of this approach is O(n!), as there are n! possible permutations of n distinct elements.

Space Complexity:

The space complexity of this approach is also O(n!), as we need to store all n! permutations in the result list. The recursive stack also consumes O(n) space.

Step by Step Implementation For Permutations

public List> permute(int[] nums) {
     // Base case
     if (nums.length == 0) {
         return new ArrayList<>();
     }
 
     // Recursive case
     List> result = new ArrayList<>();
     permuteHelper(nums, 0, result);
     return result;
 }
 
 private void permuteHelper(int[] nums, int start, List> result) {
     // Base case
     if (start == nums.length) {
         // Convert nums array to list and add to result
         List tempList = new ArrayList<>();
         for (int num : nums) {
             tempList.add(num);
         }
         result.add(tempList);
     } else {
         // Recursive case
         // For each index, swap with each element after it and recurse
         for (int i = start; i < nums.length; i++) {
             swap(nums, start, i);
             permuteHelper(nums, start + 1, result);
             swap(nums, start, i);
         }
     }
 }
 
 private void swap(int[] nums, int i, int j) {
     int temp = nums[i];
     nums[i] = nums[j];
     nums[j] = temp;
 }

def permutations(self, nums):
    res = []
    self.dfs(nums, [], res)
    return res
    
def dfs(self, nums, path, res):
    if not nums:
        res.append(path)
        # when the path has the same length as nums
        # we know that we have used all the numbers
        # in nums and we can add it to our result
    for i in xrange(len(nums)):
        self.dfs(nums[:i]+nums[i+1:], path+[nums[i]], res)
        # we use nums[:i] + nums[i+1:] to get all
        # the numbers except nums[i] and add nums[i]
        # to the end of the path

var permutations = function(nums) {
    // create an empty array to store all permutations
    const permutationList = [];
    // create a helper function to generate all permutations
    const generatePermutations = (currentPermutation, remainingNums) => {
        // if there are no remaining numbers, that means we have generated a permutation
        if (remainingNums.length === 0) {
            // so we add it to our list of permutations
            permutationList.push(currentPermutation);
        } else {
            // otherwise, we iterate through the remaining numbers
            for (let i = 0; i < remainingNums.length; i++) {
                // we create a copy of the current permutation and the remaining numbers
                const newPermutation = [...currentPermutation];
                const newRemainingNums = [...remainingNums];
                // and add the current number to the permutation
                newPermutation.push(remainingNums[i]);
                // then, we remove that number from the remaining numbers
                newRemainingNums.splice(i, 1);
                // and call the helper function again with the newly generated permutation and remaining numbers
                generatePermutations(newPermutation, newRemainingNums);
            }
        }
    };
    // we call the helper function with an empty permutation and the original array of numbers
    generatePermutations([], nums);
    // finally, we return the list of permutations
    return permutationList;
};

class Solution {
public:
    // Generate all permutations of a given string
    // Using backtracking
    vector permutations(string s) {
        // Result vector
        vector res;
        
        // Base case - empty string
        if (s.empty()) {
            res.push_back("");
            return res;
        }
        
        // Take first character and find all permutations
        // of the remaining string
        char first = s[0];
        string remaining = s.substr(1);
        vector words = permutations(remaining);
        
        // Insert the first character into all positions
        // of all the words generated by permutations(remaining)
        for (string word : words) {
            for (int i = 0; i <= word.size(); i++) {
                string temp = word;
                temp.insert(temp.begin() + i, first);
                res.push_back(temp);
            }
        }
        
        return res;
    }
};

public IList> Permute(int[] nums) { // Create a list to store the permutations IList> permutations = new List>(); // Add the first permutation (the input array) to the list permutations.Add(nums); // Loop through the list while (permutations.Count != 0) { // Get the next permutation from the list IList nextPermutation = permutations[0]; // Remove the permutation from the list permutations.RemoveAt(0); // Loop through the array for (int i = 0; i < nextPermutation.Count; i++) { // Create a new array to store the permutation int[] newPermutation = new int[nextPermutation.Count]; // Copy the permutation into the new array for (int j = 0; j < nextPermutation.Count; j++) { newPermutation[j] = nextPermutation[j]; } // Swap the elements at index i and j int temp = newPermutation[i]; newPermutation[i] = newPermutation[0]; newPermutation[0] = temp; // Add the new permutation to the list permutations.Add(newPermutation); } } // Return the list of permutations return permutations; }