东莞网站推广公司_装修企业网站建设_免费数据查询网站_营销策划运营培训机构

设⼀共有3个数，分别是1，2，3。「从前往后」考虑每⼀个数，针对当前这个数「选」或者「不选」

设计递归函数：

• 重复⼦问题：针对某⼀位，「选」或者「不选」这个数。因为最终结果要按照「字典序」输出，我们可以「先考虑不选」，然后「再考虑选」；
• 实现⽅式参考代码和注释，结合「决策树」⼀起看会很清晰

#include <bits/stdc++.h>
using namespace std;int n;
string path;void dfs(int pos)
{if (pos > n){//path存着前n个人的决策cout << path << endl;return;}//不选path += 'N';dfs(pos+1);path.pop_back(); //回溯，清空现场//选path += 'Y';dfs(pos+1);path.pop_back(); //回溯，清空现场
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n;dfs(1);return 0;
}

设n = 4, m = 3 ，「从前往后」考虑3 个位置应该选哪个数，我们可以画出如下决策树

设计递归函数：

• 重复⼦问题：当前这⼀位，应该放哪个数上去。因为这是⼀个「组合」问题，不涉及排列，所以我们当前位置开始放的数，应该是「上次决策的数的下⼀位」
• 实现⽅式参考代码和注释，结合「决策树」⼀起看会很清晰。

#include <bits/stdc++.h>
using namespace std;int n, m;
vector<int> path;void dfs(int pos, int begin)
{if (pos > m){for (auto x : path) cout << x << " ";cout << endl;return;}for (int i = begin; i <= n; i++){path.push_back(i);dfs(pos+1, i+1);path.pop_back();}
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;dfs(1, 1);return 0;
}

#include <bits/stdc++.h>
using namespace std;int n, m;
vector<int> path;void dfs(int begin)
{if (path.size() == m){for (auto x : path) cout << x << " ";cout << endl;return;}for (int i = begin; i <= n; i++){path.push_back(i);dfs(i+1);path.pop_back();}
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;dfs(1);return 0;
}

设n = 3, k = 2 ，⼀共要选出两个数，可以依次「考虑要选出来的数」是谁，画出如下决策树

设计递归函数：

• 重复⼦问题：考虑这⼀位要放上什么数。因为是「排列」问题，所以我们直接从1开始枚举要放的数。
• 剪枝：在这⼀条路径中，我们「不能选择之前已经选择过的数」。
• 实现⽅式参考代码和注释，结合「决策树」⼀起看会很清晰

#include <bits/stdc++.h>
using namespace std;const int N = 15;int n, k;
vector<int> path;
bool st[N]; //标记选过的数void dfs()
{if (path.size() == k){for (auto x : path) cout << x << " ";cout << endl;return;}for (int i = 1; i <= n; i++){if (st[i]) continue;path.push_back(i);st[i] = true;dfs();//恢复现场path.pop_back();st[i] = false;}
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> k;dfs();return 0;
}

跟上⼀道题的决策⼀样，我们可以枚举每⼀位应该放上什么数，只不过少了k的限制。剪枝的策略还是⼀样的，那就是在路径中，「不能选择之前已经选过的数」

#include <bits/stdc++.h>
using namespace std;const int N = 15;int n;
vector<int> path;
bool st[N];void dfs()
{if (path.size() == n){for (auto x : path){printf("%5d", x);        }cout << endl;return;}for (int i = 1; i <= n; i++){if (st[i]) continue;path.push_back(i);st[i] = true;dfs();path.pop_back();st[i] = false;}
}int main()
{cin >> n;dfs();return 0;
}