详解DFS求组合数+去重

无重复元素求组合数

题目描述

从 1~n 这 n 个整数中随机选出 m 个&＃xff0c;输出所有可能的选择方案。
输入格式
两个整数 n,m ,在同一行用空格隔开。
输出格式
按照从小到大的顺序输出所有方案&＃xff0c;每行1个。
首先&＃xff0c;同一行内的数升序排列&＃xff0c;相邻两个数用一个空格隔开。
其次&＃xff0c;对于两个不同的行&＃xff0c;对应下标的数一一比较&＃xff0c;字典序较小的排在前面&＃xff08;例如1 3 5 7排在1 3 6 8前面&＃xff09;。
数据范围
n>0 ,
0≤m≤n ,
n&＃43;(n−m)≤25
输入样例&＃xff1a;
5 3
输出样例&＃xff1a;
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

题解一

搜索顺序&＃xff1a;枚举每一个数&＃xff0c;每个数有选和不选两种状态&＃xff0c;枚举完所有数&＃xff0c;就能得到所有结果。

#include
#include
#include
using namespace std;int n, m;
int a[26];
bool st[26];void dfs(int u, vector<int>& path)
{if(u &＃61;&＃61; n){if(path.size() &＃61;&＃61; m){for(int i &＃61; 0; i < m; i&＃43;&＃43;){cout << path[i] << " ";}puts(" ");}return;}//选path.push_back(a[u]);dfs(u &＃43; 1, path);path.pop_back();//不选dfs(u &＃43; 1, path);
}int main()
{cin >> n >> m;for(int i &＃61; 0; i < n; i&＃43;&＃43;) a[i] &＃61; i &＃43; 1;vector<int> path;dfs(0, path);return 0;}

题解二

搜索顺序&＃xff1a;枚举m个空位&＃xff0c;每个空位有若干选择。
这里要去重一下&＃xff0c;因为是求组合数&＃xff0c; 1&＃xff0c; 2 &＃xff0c;3 和 3&＃xff0c; 2&＃xff0c; 1是同一种选择&＃xff0c;我们强制规定搜索顺序&＃xff0c;即每一个空位可以选择的数只能是上一个空位选择的数之后的数。这样就把相同的数但顺序不同的组合过滤了。

#include
#include
#include
using namespace std;int n, m;
int a[26];
bool st[26];void dfs(int u, vector<int>& path, int start)
{if(u &＃61;&＃61; m){for(int i &＃61; 0; i < m; i&＃43;&＃43;){cout << path[i] << " ";}puts(" ");return;}for(int i &＃61; start; i < n; i&＃43;&＃43;){if(!st[i]){st[i] &＃61; true;path.push_back(a[i]);dfs(u &＃43; 1, path, i &＃43; 1);path.pop_back();st[i] &＃61; false;}}
}int main()
{cin >> n >> m;for(int i &＃61; 0; i < n; i&＃43;&＃43;) a[i] &＃61; i &＃43; 1;vector<int> path;dfs(0, path, 0);return 0;
}

有重复元素求组合数

题目描述

给定一个长度为 n 的可包含重复数字的序列&＃xff0c;从中随机选取 m 个数字&＃xff0c;输出所有可能的选择方案。
输入格式
第一行包含两个整数 n,m。
第二行包含 n 个正整数。
输出格式
按照从小到大的顺序输出所有方案&＃xff0c;每行 1 个。
首先&＃xff0c;同一行内的数升序排列&＃xff0c;相邻两个数用一个空格隔开。
其次&＃xff0c;对于两个不同的行&＃xff0c;对应下标的数一一比较&＃xff0c;字典序较小的排在前面&＃xff08;例如1 3 5 7排在1 3 6 8前面&＃xff09;。
数据范围
n>0,
0≤m≤n,
n&＃43;(n−m)≤25,
序列内所有元素均不大于 n。
输入样例&＃xff1a;
5 3
1 2 2 3 3
输出样例&＃xff1a;
1 2 2
1 2 3
1 3 3
2 2 3
2 3 3

题解一

搜索顺序&＃xff1a;枚举每一个数&＃xff0c;由于有重复的数字&＃xff0c;所以不能按照每一个数选与不选枚举&＃xff0c;比如有三个数字1,2,2&＃xff0c;若按照这种顺序&＃xff0c;1,2会枚举到两次&＃xff0c;因此应该按照某一个数选几个枚举。

#include
#include
#include
#include using namespace std;const int N &＃61; 30;int n, m;
int a[N], path[N];void dfs(int u, int s) // u代表选到了a[u]&＃xff0c;s代表当前选了几个数
{if (s &＃61;&＃61; m){for (int i &＃61; 0; i < m; i&＃43;&＃43;) cout << path[i] << " ";cout << endl;return;}if (s > m) return;if (u > n) return;int k &＃61; u;while (k <&＃61; n && a[k] &＃61;&＃61; a[u]) k&＃43;&＃43;;int cnt &＃61; k - u;for (int i &＃61; cnt; i >&＃61; 0; i--) // 由于输出时要按照字典序输出&＃xff0c;所以我们按照从多到少循环&＃xff0c;{ // 小的数越多&＃xff0c;字典序就越小for (int j &＃61; u; j < u &＃43; i; j&＃43;&＃43;)path[s &＃43; j - u] &＃61; a[u];dfs(k, s &＃43; i);}}int main()
{cin >> n >> m;for (int i &＃61; 1; i <&＃61; n; i&＃43;&＃43;) cin >> a[i];sort(a &＃43; 1, a &＃43; 1 &＃43; n);dfs(1, 0);return 0;
}

题解二

搜索顺序&＃xff1a;枚举m个空位&＃xff0c;每个空位有若干选择。
这里要去重一下&＃xff0c;因为是求组合数&＃xff0c; 1&＃xff0c; 2 &＃xff0c;3 和 3&＃xff0c; 2&＃xff0c; 1是同一种选择&＃xff0c;我们强制规定搜索顺序&＃xff0c;即每一个空位可以选择的数只能是上一个空位选择的数之后的数。这样就把相同的数但顺序不同的组合过滤了。
重复元素去重&＃xff1a;

#include
#include
#include
using namespace std;int n, m;
int a[26];
bool st[26];void dfs(int u, vector<int>& path, int start)
{if(u &＃61;&＃61; m){for(int i &＃61; 0; i < m; i&＃43;&＃43;){cout << path[i] << " ";}puts(" ");return;}for(int i &＃61; start; i < n; i&＃43;&＃43;){//关键代码&＃xff1a;如图一解释// used[i - 1] &＃61;&＃61; true&＃xff0c;说明同一树支a[i - 1]使用过 // used[i - 1] &＃61;&＃61; false&＃xff0c;说明同一树层a[i - 1]使用过// 而我们要对同一树层使用过的元素进行跳过if(i > 0 && a[i] &＃61;&＃61; a[i - 1] && !st[i - 1]){continue;}//效果与上面的一样/*if(i > start && a[i] &＃61;&＃61; a[i - 1]){continue;}*/st[i] &＃61; true;path.push_back(a[i]);dfs(u &＃43; 1, path, i &＃43; 1);path.pop_back();st[i] &＃61; false;}
}int main()
{cin >> n >> m;for(int i &＃61; 0; i < n; i&＃43;&＃43;) cin >> a[i];vector<int> path;sort(a, a &＃43; n);dfs(0, path, 0);return 0;}

参考&＃xff1a;

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/