从 1~n 这 n 个整数中随机选出 m 个，输出所有可能的选择方案。 输入格式 两个整数 n,m ,在同一行用空格隔开。 输出格式 按照从小到大的顺序输出所有方案，每行1个。 首先，同一行内的数升序排列，相邻两个数用一个空格隔开。 其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如1 3 5 7排在1 3 6 8前面）。 数据范围 n>0 , 0≤m≤n , n+(n−m)≤25 输入样例： 5 3 输出样例： 1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5
搜索顺序：枚举每一个数，每个数有选和不选两种状态，枚举完所有数，就能得到所有结果。
#include <iostream> #include <algorithm> #include <vector> using namespace std; int n, m; int a[26]; bool st[26]; void dfs(int u, vector<int>& path) { if(u == n) { if(path.size() == m) { for(int i = 0; i < m; i++) { cout << path[i] << " "; } puts(" "); } return; } //选 path.push_back(a[u]); dfs(u + 1, path); path.pop_back(); //不选 dfs(u + 1, path); } int main() { cin >> n >> m; for(int i = 0; i < n; i++) a[i] = i + 1; vector<int> path; dfs(0, path); return 0; }搜索顺序：枚举m个空位，每个空位有若干选择。 这里要去重一下，因为是求组合数， 1， 2 ，3 和 3， 2， 1是同一种选择，我们强制规定搜索顺序，即每一个空位可以选择的数只能是上一个空位选择的数之后的数。这样就把相同的数但顺序不同的组合过滤了。
#include <iostream> #include <algorithm> #include <vector> using namespace std; int n, m; int a[26]; bool st[26]; void dfs(int u, vector<int>& path, int start) { if(u == m) { for(int i = 0; i < m; i++) { cout << path[i] << " "; } puts(" "); return; } for(int i = start; i < n; i++) { if(!st[i]) { st[i] = true; path.push_back(a[i]); dfs(u + 1, path, i + 1); path.pop_back(); st[i] = false; } } } int main() { cin >> n >> m; for(int i = 0; i < n; i++) a[i] = i + 1; vector<int> path; dfs(0, path, 0); return 0; }给定一个长度为 n 的可包含重复数字的序列，从中随机选取 m 个数字，输出所有可能的选择方案。 输入格式 第一行包含两个整数 n,m。 第二行包含 n 个正整数。 输出格式 按照从小到大的顺序输出所有方案，每行 1 个。 首先，同一行内的数升序排列，相邻两个数用一个空格隔开。 其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如1 3 5 7排在1 3 6 8前面）。 数据范围 n>0, 0≤m≤n, n+(n−m)≤25, 序列内所有元素均不大于 n。 输入样例： 5 3 1 2 2 3 3 输出样例： 1 2 2 1 2 3 1 3 3 2 2 3 2 3 3
搜索顺序：枚举每一个数，由于有重复的数字，所以不能按照每一个数选与不选枚举，比如有三个数字1,2,2，若按照这种顺序，1,2会枚举到两次，因此应该按照某一个数选几个枚举。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 30; int n, m; int a[N], path[N]; void dfs(int u, int s) // u代表选到了a[u]，s代表当前选了几个数 { if (s == m) { for (int i = 0; i < m; i++) cout << path[i] << " "; cout << endl; return; } if (s > m) return; if (u > n) return; int k = u; while (k <= n && a[k] == a[u]) k++; int cnt = k - u; for (int i = cnt; i >= 0; i--) // 由于输出时要按照字典序输出，所以我们按照从多到少循环， { // 小的数越多，字典序就越小 for (int j = u; j < u + i; j++) path[s + j - u] = a[u]; dfs(k, s + i); } } int main() { cin >> n >> m; for (int i = 1; i <= n; i++) cin >> a[i]; sort(a + 1, a + 1 + n); dfs(1, 0); return 0; }搜索顺序：枚举m个空位，每个空位有若干选择。 这里要去重一下，因为是求组合数， 1， 2 ，3 和 3， 2， 1是同一种选择，我们强制规定搜索顺序，即每一个空位可以选择的数只能是上一个空位选择的数之后的数。这样就把相同的数但顺序不同的组合过滤了。 重复元素去重：
#include <iostream> #include <algorithm> #include <vector> using namespace std; int n, m; int a[26]; bool st[26]; void dfs(int u, vector<int>& path, int start) { if(u == m) { for(int i = 0; i < m; i++) { cout << path[i] << " "; } puts(" "); return; } for(int i = start; i < n; i++) { //关键代码：如图一解释 // used[i - 1] == true，说明同一树支a[i - 1]使用过 // used[i - 1] == false，说明同一树层a[i - 1]使用过 // 而我们要对同一树层使用过的元素进行跳过 if(i > 0 && a[i] == a[i - 1] && !st[i - 1]) { continue; } //效果与上面的一样 /*if(i > start && a[i] == a[i - 1]) { continue; }*/ st[i] = true; path.push_back(a[i]); dfs(u + 1, path, i + 1); path.pop_back(); st[i] = false; } } int main() { cin >> n >> m; for(int i = 0; i < n; i++) cin >> a[i]; vector<int> path; sort(a, a + n); dfs(0, path, 0); return 0; }https://leetcode-cn.com/problems/subsets-ii/solution/90-zi-ji-iiche-di-li-jie-zi-ji-wen-ti-ru-he-qu-zho/
https://www.acwing.com/blog/content/2131/
