1. 问题
2. 思路
3. 代码实现
#if 0
class Solution
{
private:
vector<int> path; // 满足条件的一个结果
vector<vector<int>> res; // 结果集
void backtracking(vector<int> nums, vector<bool> used)
{
// 若path的个数和nums个数相等,说明得到一个结果
if(path.size() == nums.size())
{
res.push_back(path);
return ;
}
for(int i = 0; i < nums.size(); i++)
{
if(used[i] == true) // 已经选过,跳过
{
continue;
}
used[i] = true; // 选择
path.push_back(nums[i]); // 加入元素
backtracking(nums, used); // 进入下一层循环
path.pop_back(); // 回溯, 去掉元素
used[i] = false; // 回溯,撤销选择
}
}
public:
vector<vector<int>> permute(vector<int>& nums)
{
path.clear();
res.clear();
vector<bool> used(nums.size(), false);
backtracking(nums, used);
return res;
}
};
#endif
//效率比较高的代码
///
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums)
{
dfs(nums, path, res);
return res;
}
void dfs (vector<int> &nums, vector<int> &path, vector<vector<int>> &res)
{
// 触发结束条件
if (path.size() == nums.size())
{
res.push_back(path);
return;
}
for (vector<int>::size_type i = 0; i < nums.size(); ++i)
{
// 做选择,通过nums和path推测出选择列表
vector<int>::iterator iter = find(path.begin(), path.end(), nums[i]);
if (iter != path.end())
{ // 如果nums[i]已经出现在path中,则应跳过,否则加到path中(排除不合法选择)
continue;
}
path.push_back(nums[i]);
// 递归调用
dfs(nums, path, res);
// 撤销选择
path.pop_back();
}
}
private:
vector<int> path; // 一次遍历路径
vector<vector<int>> res; // 所有符合路径集合
};
4. 测试结果