Table of Contents
Given a collection of distinct integers, nums, return all possible permutations of the integers.
Sample Input/Output:
Let’s consider a sample input:
nums = [1, 2, 3]
Expected Output:
[
[1, 2, 3],
[1, 3, 2],
[2, 1, 3],
[2, 3, 1],
[3, 1, 2],
[3, 2, 1]
]
Explanation:
For the given input [1, 2, 3], all possible permutations are [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]].
Time and Space Complexity:
The time complexity of the solution will be O(N!), where N is the number of elements in the input array nums. This is because there are N! possible permutations for an array of N elements.
The space complexity will also be O(N!), as we need to store all the permutations.
Now, let’s implement the solution in C++:
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> result;
vector<int> permutation;
vector<bool> used(nums.size(), false); // Keep track of used elements
// Helper function to backtrack and generate permutations
void backtrack(vector<int>& nums, vector<int>& permutation, vector<bool>& used, vector<vector<int>>& result) {
// If the permutation is complete, add it to the result
if (permutation.size() == nums.size()) {
result.push_back(permutation);
return;
}
for (int i = 0; i < nums.size(); ++i) {
if (used[i]) continue; // Skip used elements
permutation.push_back(nums[i]); // Add the current element to the permutation
used[i] = true; // Mark the element as used
backtrack(nums, permutation, used, result); // Recursive call for the next element
used[i] = false; // Backtrack: unmark the element as used
permutation.pop_back(); // Backtrack: remove the last element to explore other permutations
}
}
backtrack(nums, permutation, used, result);
return result;
}
int main() {
vector<int> nums = {1, 2, 3};
vector<vector<int>> result = permute(nums);
cout << "Permutations:\n";
for (const vector<int>& permutation : result) {
cout << "[";
for (int num : permutation) {
cout << num << " ";
}
cout << "]" << endl;
}
return 0;
}
In this implementation, we use backtracking to generate all possible permutations. The backtrack function is a recursive function that generates permutations by exploring all possible choices for each position in the permutation. It uses a used array to keep track of the elements already used in the current permutation.
The main function demonstrates the usage of permute by finding all possible permutations for the given input nums.
The output for the provided test case will be:
Permutations:
[1 2 3 ]
[1 3 2 ]
[2 1 3 ]
[2 3 1 ]
[3 1 2 ]
[3 2 1 ]