Given a collection of distinct integers, return all possible permutations.
Example:
Input: [1,2,3] Output: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
給你一串彼此不同的數字，把所有排列可能印出來。
[Solution]
Just Imagine we have "N slots" for these N distinct numbers.
So what we need to do is :
decide which of the remaining numbers should be put into slot 1
decide which of the remaining numbers should be put into slot 2
...
decide which of the remaining numbers should be put into slot N
After all slots have been occupied, then we have a permutation.
For example :
pick 3 from [1,2,3] and put into slot 1 --> [3, , ]
pick 1 from [1,2] and put into slot 1 --> [3,1, ]
[Advance Solution]
"We need to pick a number from the remaining numbers, for each slot."
But how do you know who are those remaining numbers ? ?
In the previous solution, we use an array "picked" to keep track of who did not been picked.
Now we are going to improve that.
The key point of advanced idea is :
We connect the idea of "remaining" to the "position of number in original array".
We want every picked numbers been put to the left of original array,
and every remaining numbers been put to the right of original array.
So we just need to memorize the point which separate them, then we will be able to know who are those remaining numbers.
To achieve that, in each decision process of current slot, we simply swap the chosen number with the one in the current slot.
For example:
pick 3 from [1,2,3] and put into slot 1 :
swap '3' with the one in slot 1 (which is '1')
the original array become [3,2,1].
Remaining number are on the right of slot1
pick 1 from [3,2,1] and put into slot 2 :
swap '1' with the one in slot2 (which is '2')
the original array become [3,1,2].
Remaining number are on the right of slot2
pick 2 from [3,1,2] and put into slot 3 :
swap '2' with the one in slot3 (which is '2')
the original array become [3,1,2],
Remaining number are on the right of slot3
We started from left to right, and continue swapping non-picked number to the right.
So we can be sure that the remaining numbers are on the right of the current slot.
After all slots have been occupied, then we have a permutation.
For example :
pick 3 from [1,2,3] and put into slot 1 --> [3, , ]
pick 1 from [1,2] and put into slot 1 --> [3,1, ]
pick 2 from [2] and put into slot 1 --> [3,1,2] we have a permutation
Let's make a brief summary:
We need to pick a number from the remaining numbers, for each slot.
We can use recursive function to achieve the goal.
Every recursive level represent a deciding process for a slot.
(level 1 for slot 1, level 2 for slot 2,...)
After picking a number for this slot, we do a recursive call to trigger the deciding process for next slot. When N slots is occupied (or N numbers have been picked, it's the same), we stop.
-----
Let's make a brief summary:
We need to pick a number from the remaining numbers, for each slot.
We can use recursive function to achieve the goal.
Every recursive level represent a deciding process for a slot.
(level 1 for slot 1, level 2 for slot 2,...)
After picking a number for this slot, we do a recursive call to trigger the deciding process for next slot. When N slots is occupied (or N numbers have been picked, it's the same), we stop.
-----
class Solution {
public:
void buildpermute(vector<int>& nums,
vector<bool>& picked,
vector<int>& permutation,
vector<vector<int>>& res)
{
if(permutation.size()==nums.size())
{
res.push_back(permutation);
return;
}
for(int i=0; i<nums.size(); i++)
{
if(picked[i]==false)
{
picked[i]=true;
permutation.push_back(nums[i]);
buildpermute(nums,picked,permutation,res);
permutation.pop_back();
picked[i]=false;
}
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<bool> picked(nums.size(), false);
vector<int> permutation;
vector<vector<int>> res;
buildpermute(nums, picked, permutation, res);
return res;
}
};
"We need to pick a number from the remaining numbers, for each slot."
But how do you know who are those remaining numbers ? ?
In the previous solution, we use an array "picked" to keep track of who did not been picked.
Now we are going to improve that.
The key point of advanced idea is :
We connect the idea of "remaining" to the "position of number in original array".
We want every picked numbers been put to the left of original array,
and every remaining numbers been put to the right of original array.
So we just need to memorize the point which separate them, then we will be able to know who are those remaining numbers.
To achieve that, in each decision process of current slot, we simply swap the chosen number with the one in the current slot.
For example:
pick 3 from [1,2,3] and put into slot 1 :
swap '3' with the one in slot 1 (which is '1')
the original array become [3,2,1].
Remaining number are on the right of slot1
pick 1 from [3,2,1] and put into slot 2 :
swap '1' with the one in slot2 (which is '2')
the original array become [3,1,2].
Remaining number are on the right of slot2
swap '2' with the one in slot3 (which is '2')
the original array become [3,1,2],
Remaining number are on the right of slot3
We started from left to right, and continue swapping non-picked number to the right.
So we can be sure that the remaining numbers are on the right of the current slot.
void buildpermute2(vector<int>& nums,
int curslot,
vector<vector<int>>& res){
if(curslot==nums.size()){
res.push_back(nums);
return;
}
for(int i=curslot; i<nums.size(); i++){
swap(nums[curslot], nums[i]);
buildpermute2(nums, curslot+1 ,res);
swap(nums[curslot], nums[i]);
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> res;
buildpermute2(nums, 0 ,res);
return res;
}
