Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
41 lines (37 sloc) 1.01 KB
problem:
Given a collection of numbers, return all possible permutations.
For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].
----------------------------------------------------------
solution:
void dfs(int depth, vector<int>& num, vector<int> &tmp, vector<vector<int> > &ret, vector<bool> &isVisited)
{
if(depth == num.size())
{
ret.push_back(tmp);
return;
}
for(int i = 0; i < num.size(); i++)
{
if(isVisited[i] == false)
{
isVisited[i] = true;
tmp.push_back(num[i]);
dfs(depth + 1, num, tmp, ret, isVisited);
tmp.pop_back();
isVisited[i] = false;
}
}
}
vector<vector<int> > permute(vector<int> &num)
{
vector<vector<int> > ret;
if(num.size() == 0)
return ret;
sort(num.begin(), num.end());
vector<bool> isVisited(num.size(), false);
vector<int> tmp;
dfs(0, num, tmp, ret, isVisited);
return ret;
}