加上有重复数字之后还是挺麻烦的😑😐
- 1.递归找子集：$2^n$
①：无重复数字，题目链接
②：有重复数字，题目链接 - 2.递归找排列数：$n!$
①：无重复数字，题目链接
②：有重复数字，题目链接 - 3.递归找组合数：$C_n^m$
①：无重复数字，题目链接
②：有重复数字，题目链接
找子集
无重复数字
对于每一个数都有选与不选两种选择，所以是指数级别。
C++代码
#include <bits/stdc++.h>
using namespace std;
const int N = 20;
int n;
bool st[N];
void dfs(int u)
{
if (u > n)
{
for (int i = 1; i <= n; i++)
if (st[i]) cout << i << " ";
cout << endl;
return;
}
// 不选u
st[u] = false;
dfs(u + 1);
// 选u
st[u] = true;
dfs(u + 1);
}
int main()
{
cin >> n;
dfs(1);
return 0;
}
有重复数字
由于有重复的数字，所以不能按照每一个数选与不选枚举，比如有三个数字1,2,2，若按照这种顺序，1,2会枚举到两次，因此应该按照某一个数选几个枚举。
C++代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 20;
int n;
int a[N];
bool st[N];
void dfs(int u)
{
if (u == n)
{
for (int i = 0; i < n; i++)
if (st[i]) cout << a[i] << " ";
cout << endl;
return;
}
int k = u;
while (k < n && a[k] == a[u]) k++;
// a[u]这个数一个都不选
dfs(k);
// a[u]这个数选一个，选两个，....
for (int i = u; i < k; i++)
{
st[i] = true;
dfs(k);
}
for (int i = u; i < k; i++)
st[i] = false;
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
sort(a, a + n);
dfs(0);
return 0;
}
找排列数
无重复数字
按照每个位置选哪个数字枚举。
C++代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 12;
int n;
int a[N];
bool st[N];
void dfs(int u)
{
if (u > n)
{
for (int i = 1; i <= n; i++) cout << a[i] << " ";
cout << endl;
return;
}
for (int i = 1; i <= n; i++)
{
if (!st[i])
{
st[i] = true;
a[u] = i;
dfs(u + 1);
st[i] = false;
}
}
}
int main()
{
cin >> n;
dfs(1);
return 0;
}
有重复数字
比如：1,1,2，为了方便起见写成：1,1’,2。
若是按照上面的方式，则会有六种：
1 1' 2
1' 1 2
1' 1 2
1' 2 1
2 1 1'
2 1' 1
这是因为考虑了相同的数的顺序，所以我们应该人为的规定相同数字的顺序，最简单的就是按照原本的顺序排列。例如：1,1,1,2，在选第一个位置填哪一个数时，我们循环遍历所有的数字，第一次选择第一个1以后，我们需要将后面的1跳过。若不跳过，就会出现后面的1跑到第一个1的前面的情况。
C++代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 15;
int n;
int a[N], nums[N];
bool st[N];
void dfs(int u)
{
if (u == n)
{
for (int i = 0; i < n; i++) cout << nums[i] << " ";
cout << endl;
return;
}
for (int i = 0; i < n; i++)
{
if (!st[i])
{
st[i] = true;
nums[u] = a[i];
dfs(u + 1);
st[i] = false;
while (i < n && a[i] == a[i + 1])
i++;
}
}
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
sort(a, a + n);
dfs(0);
return 0;
}
找组合数
无重复数字
有两种枚举方式，第一种为按照位置枚举，第二种为按照数字枚举。
按照位置C++代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 30;
int n, m;
int a[N];
void dfs(int u)
{
if (u > m)
{
for (int i = 1; i <= m; i++) cout << a[i] << " ";
cout << endl;
return;
}
for (int i = a[u - 1] + 1; i <= n; i++) // 选比上一个数字大的第一个数
{
a[u] = i;
dfs(u + 1);
}
}
int main()
{
cin >> n >> m;
a[0] = 0; // 边界设置成无穷小，本题0即可
dfs(1);
return 0;
}
按照数字C++代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 30;
int n, m;
int a[N];
void dfs(int u, int s) // u代表u这个数，s代表当前选了几个数
{
if (s == m)
{
for (int i = 0; i < m; i++) cout << a[i] << " ";
cout << endl;
return;
}
if (s > m) return;
if (u > n) return;
// 选u
a[s] = u;
dfs(u + 1, s + 1);
// 不选u
dfs(u + 1, s);
}
int main()
{
cin >> n >> m;
dfs(1, 0);
return 0;
}
有重复数字
思路与找子集中有重复数字的做法相同，当遇到相同的数时，枚举选几个。
C++代码
#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;
}
