algoadvance

Leetcode 46. Permutations

Problem Statement

You are given an array of distinct integers, nums. Return all possible permutations of the elements in nums.

Example:

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

Constraints:

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

Clarifying Questions

1. Q: Can the input array contain duplicated elements? A: No, the array of integers is distinct as per the problem statement.

2. Q: What should we return if the input array is empty? A: According to the constraint 1 <= nums.length, we can assume the array won’t be empty.

Strategy

1. Backtracking Approach:
   • Use backtracking to generate all permutations.
   • Create a list to store the current permutation and a boolean array to keep track of visited elements.
   • Recursively add elements to the current permutation until its size matches the input array size.
   • When the permutation is complete, add it to the result list.
   • Backtrack by setting the current element as unvisited and removing it from the current permutation.

Code

#include <vector>

class Solution {
public:
    void backtrack(std::vector<int>& nums, std::vector<bool>& visited, std::vector<int>& current, std::vector<std::vector<int>>& result) {
        if (current.size() == nums.size()) {
            result.push_back(current);
            return;
        }
        
        for (int i = 0; i < nums.size(); ++i) {
            if (!visited[i]) {
                visited[i] = true;
                current.push_back(nums[i]);
                
                backtrack(nums, visited, current, result);
                
                current.pop_back();
                visited[i] = false;
            }
        }
    }
    
    std::vector<std::vector<int>> permute(std::vector<int>& nums) {
        std::vector<std::vector<int>> result;
        std::vector<int> current;
        std::vector<bool> visited(nums.size(), false);
        
        backtrack(nums, visited, current, result);
        
        return result;
    }
};

Time Complexity

• The algorithm generates all possible permutations of the given array.
• The total number of permutations of an array with n elements is n!.
• For each permutation, it takes O(n) time to copy it to the result list.
• Therefore, the overall time complexity is O(n * n!).

Space Complexity

• The space complexity is also O(n * n!) for storing all the permutations.
• Additionally, the active stack frames and the visited array use O(n) extra space.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?