点名

未分类

1
2
3 ╳
4
5 ╳
6 ╳
7 ╳
8 ╳
10 ╳
11
12 ╳
13
15 ╳
16
17 ╳
18 ╳
19
20 ╳
21 ╳
22
23
25
26 ╳
27 ╳
28
29
30 ╳
31 ╳
44

代码
// LeetCode, Permutations
// 深搜，增量构造法
// 时间复杂度 O(n!)，空间复杂度 O(n)
class Solution {
public:
vector > permute(vector& num) {
sort(num.begin(), num.end());
vector> result;
vector path; // 中间结果
dfs(num, path, result);
return result;
}
private:
void dfs(const vector& num, vector &path,
vector > &result) {
if (path.size() == num.size()) { // 收敛条件
result.push_back(path);
return;
}

// 扩展状态
for (auto i : num) {
// 查找 i 是否在 path 中出现过
auto pos = find(path.begin(), path.end(), i);
if (pos == path.end()) {
path.push_back(i);
dfs(num, path, result);
path.pop_back();
}
}
}
};
相关题目