46. Permutations
难度:Medium
刷题内容
原题连接
- https://leetcode.com/problems/permutations/
内容描述
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]
]
˼·1 *- ʱ�临�Ӷ�: O(n!n)*- �ռ临�Ӷ�: O(n)***
�ܲ����Ŀ���ݹ��һ���⣬ÿ�ζ�����һ����֮内容描述����ɡ�
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int> > ans;
if(!nums.size())
return ans;
if(nums.size() == 1)
ans.push_back(nums);
for(int i = 0;i < nums.size();++i)
{
swap(nums[0],nums[i]);
vector<int> v(nums.begin() + 1,nums.end());
vector<vector<int> > ret = permute(v);
for(int i = 0;i < ret.size();++i)
{
ret[i].push_back(nums[0]);
ans.push_back(ret[i]);
}
swap(nums[0],nums[i]);
}
return ans;
}
};
˼·2 **- ʱ�临�Ӷ�: O(n!)*- �ռ临�Ӷ�: O(n)***
���ǿ��Զ�������㷨�����Ż�����DFS�ķ�����ÿ�μ�¼�Ѿ内容描述����ֽ��еݹ鼴��
class Solution {
public:
void DFS(int* visited,vector<int>& nums,vector<vector<int> >& ans,vector<int> temp)
{
int count1 = 0;
for(int i = 0;i < nums.size();++i)
if(!visited[i])
{
temp.push_back(nums[i]);
visited[i] = 1;
DFS(visited,nums,ans,temp);
temp.pop_back();
visited[i] = 0;
count1 = 1;
}
if(!count1)
ans.push_back(temp);
}
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int> > ans;
int visited[nums.size()];
memset(visited,0,sizeof(visited));
vector<int> temp;
for(int i = 0; i < nums.size();++i)
{
visited[i] = 1;
temp.push_back(nums[i]);
DFS(visited,nums,ans,temp);
temp.pop_back();
visited[i] = 0;
}
return ans;
}
};
