0046. Permutations¶
Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.
Example 1:
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Example 2:
Input: nums = [0,1]
Output: [[0,1],[1,0]]
Example 3:
Input: nums = [1]
Output: [[1]]
Constraints:
1 <= nums.length <= 6-10 <= nums[i] <= 10- All the integers of
numsare unique.
Analysis¶
Traditional DFS¶
There are two recursive ways to solve this problem. One way is the traditional DFS with the help of using an additional memory to record any existed configuration. For each iteration, we use an index to locate which index we are going to place our number, and the base case is when this index reaches the end. When placing our number to this index, we should try out all the numbers from nums[0] to nums[end], and compare them with the current visited memory to decide if we can put that number to the index. This process for each iteration will take up O(n) complexity, and there will be n! results at the bottom level, so the total time complexity is O(n \times n!)
Using Swap¶
We could also use a different way to generate each configuration by using a swap operation. For each iteration, we require an index to represent: from nums[0] to nums[i] we will maintain the current order, and starting from i + 1 we will start to swap with each j where j is in [i + 1, n) , so that it could help to eliminate the visited memory. However, the time complexity is still O(n \times n!)
Code¶
Method 1¶
class Solution {
public:
vector<vector<int>> ret;
vector<vector<int>> permute(vector<int>& nums) {
helper ({}, nums);
return ret;
}
void helper (vector<int> curr, vector<int>& nums)
{
if (curr.size () == nums.size ())
ret.push_back (curr);
else
{
unordered_set<int> s(curr.begin (), curr.end ());
for (int i = 0; i < nums.size (); ++i)
{
if (s.find (nums[i]) != s.end ())
continue;
else
{
curr.push_back (nums[i]);
helper (curr, nums);
curr.pop_back ();
}
}
}
}
};
Code 2¶
class Solution {
public:
vector<vector<int>> res;
void h(vector<int> curr, int index) {
if (index == curr.size()) {
res.push_back(curr);
return;
}
for (int i = index; i < curr.size(); ++i) {
swap(curr[i], curr[index]);
h(curr, index + 1);
swap(curr[i], curr[index]);
}
}
vector<vector<int>> permute(vector<int>& nums) {
h(nums, 0);
return res;
}
};