Description
Given a collection of distinct numbers, return all possible permutations.
Example
[1,2,3] have the following permutations: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
Discussion
给定一个整数数组，求该数组的全排列
这个问题可以采用深度优先搜索的方法来做。另外，需要用一个usedPos的数组来记录已经使用过的数字位置。
C++ Code
class Solution {
public:
/**
深度优先搜索给出所有序列
@param nums 输入数列
@param answer 最终结果
@param subAnswer 最终答案的子答案
@param usedPos 已经使用过的数字
@param level 深度优先搜索树的深度
*/
void dfs(vector<int> & nums, vector<vector<int>> & answer, vector<int> & subAnswer, vector<int> usedPos, int level)
{
if (level >= nums.size())
{
answer.push_back(subAnswer);
return;
}
for(int i = 0; i < nums.size(); i++)
{
if(usedPos[i] == 0)
{
usedPos[i] = 1;
subAnswer.push_back(nums[i]);
dfs(nums, answer, subAnswer, usedPos, level + 1);
usedPos[i] = 0;
subAnswer.pop_back();
}
}
}
vector<vector<int>> permute(vector<int> & nums) {
vector<vector<int>> answer;
if(nums.size() == 0)
{
return answer;
}
vector<int> subAnswer;
vector<int> usedPos(nums.size(), 0);
dfs(nums, answer, subAnswer, usedPos, 0);
return answer;
}
};