递归找子集、排列数与组合数总结
2020-04-05 18:28:17 #DS & Algorithms
本文总阅读量次

找子集

无重复数字

对于每一个数都有选与不选两种选择，所以是指数级别。

C++代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#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++代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#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++代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#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
2
3
4
5
6
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++代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#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++代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#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++代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#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++代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#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;
}

参考

AcWing笔试面试辅导课

上一页
2020-04-05 18:28:17 #DS & Algorithms
下一页