Keyboard shortcuts

Press or to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Permutations 🧠

LeetCode Link: Permutations

Difficulty: Medium

Problem Explanation 📝

Problem: LeetCode 46 - Permutations

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

Intuition: To find all possible permutations of a given array, we can use a backtracking approach. The idea is to generate all possible arrangements by trying out different elements at each step. We explore each element, including it in the current permutation if it hasn't been used before. By backtracking, we generate all valid permutations.

Approach:

  1. Initialize an empty vector permutation to store the current permutation.
  2. Initialize an empty vector result to store all valid permutations.
  3. Define a helper function backtrack:
  • If the size of the current permutation is equal to the size of the input array nums, add the current permutation to the result vector.
  • Otherwise:
  • Iterate through the elements in the input array nums:
  • If the current element is already in the permutation, skip it to avoid duplicates.
  • Include the current element in the permutation.
  • Recursively call backtrack with the updated permutation.
  • Exclude the current element from the permutation (backtrack).
  1. Call the backtrack function with an empty permutation.
  2. Return the result vector containing all valid permutations.

Time Complexity: The time complexity is O(N!), where N is the size of the input array nums. This is because there are N! possible permutations, and we generate all of them.

💾 Space Complexity: The space complexity is O(N), where N is the size of the input array nums. This is because we store the permutations in the result vector.

Solutions 💡

Cpp 💻

class Solution {
  public:
    vector<vector<int>> permute(vector<int> &nums) {
        vector<vector<int>> result;
        vector<int> permutation;
        vector<bool> used(nums.size(), false);  // Track used elements to avoid duplicates
        backtrack(nums, used, permutation, result);
        return result;
    }

  private:
    void backtrack(const vector<int> &nums, vector<bool> &used, vector<int> &permutation, vector<vector<int>> &result) {
        if (permutation.size() == nums.size()) {
            result.push_back(permutation);
            return;
        }

        for (int i = 0; i < nums.size(); ++i) {
            if (used[i]) {
                continue;  // Skip already used elements
            }

            used[i] = true;  // Mark the current element as used
            permutation.push_back(nums[i]);  // Include the current element in the permutation
            backtrack(nums, used, permutation, result);  // Recursively call with updated permutation
            permutation.pop_back();  // Exclude the current element (backtrack)
            used[i] = false;  // Mark the current element as unused for other permutations
        }
    }
};

// class Solution {
// public:
//     vector<vector<int>> permute(vector<int>& nums) {
//         vector<vector<int>> result;
//         backtrack(result, nums, 0);
//         return result;
//     }
// private:
//     void backtrack(vector<vector<int>> &result, vector<int> &nums, int start) {
//         if(start == nums.size()) {
//             result.push_back(nums);
//             return;
//         }

//         for(int i = start; i < nums.size(); i++) {
//             // swapping allows us to explore all possible permutations by considering different elements at the current position.
//             // since start is zero we will swap indices, [0, 1], 0, 2], ... , [0, n-1]
//             swap(nums[i], nums[start]);
//             backtrack(result, nums, start+1);
//             // Once we come out of the recursion, we backtrack by swapping back the elements at indices start and i. This is necessary to restore the original order of elements and avoid duplicates.
//             swap(nums[i], nums[start]);
//         }
//     }
// };

Python 🐍

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def backtrack(start):
            if start == len(nums) - 1:
                permutations.append(nums[:])  # Append a copy of the current permutation

            for i in range(start, len(nums)):
                nums[start], nums[i] = nums[i], nums[start]  # Swap elements
                backtrack(start + 1)
                nums[start], nums[i] = nums[i], nums[start]  # Backtrack

        permutations = []
        backtrack(0)
        return permutations