Sponsored
Sponsored
This approach uses recursion combined with backtracking to generate all possible permutations of the input array. The algorithm works by swapping elements of the array and recursively building permutations by fixing one element at a time until the entire array is permutated.
Time Complexity: O(n * n!) as there are n! permutations and we copy each permutation.
Space Complexity: O(n!) for storing the permutations, plus additional space used by the recursive stack.
1function permute(nums) {
2 const result = [];
3 const backtrack = (path) => {
4 if (path.length === nums.length) {
5 result.push([...path]);
6 return;
7 }
8 for (const num of nums) {
9 if (!path.includes(num)) {
10 path.push(num);
11 backtrack(path);
12 path.pop();
13 }
14 }
15 };
16 backtrack([]);
17 return result;
18}
19
20console.log(permute([1, 2, 3]));
21This JavaScript implementation creates permutations using a recursive backtracking approach. A temporary path array is used to store current permutations, and once a complete permutation is built, it is added to the results.
An alternative iterative approach utilizes a queue to generate permutations level by level by inserting each number at every possible position within every possible permutation.
Time Complexity: O(n * n!), iterating through permutations.
Space Complexity: O(n!) for storing permutations, constant space for current permutation array.
1#include <vector>
#include <iostream>
#include <algorithm>
std::vector<std::vector<int>> permute(std::vector<int>& nums) {
std::vector<std::vector<int>> result;
std::sort(nums.begin(), nums.end());
do {
result.push_back(nums);
} while (std::next_permutation(nums.begin(), nums.end()));
return result;
}
int main() {
std::vector<int> nums = {1, 2, 3};
std::vector<std::vector<int>> result = permute(nums);
for (const auto& perm : result) {
for (int num : perm) {
std::cout << num << " ";
}
std::cout << '\n';
}
return 0;
}
This C++ solution efficiently generates permutations using the next_permutation library function, producing ordered permutations by iterating and modifying them directly.