【每日一题 春季13】93. 递归实现组合型枚举 & 90. 子集 II

发表于 更新于 分类于 Valine：
本文字数： 114 阅读时长 ≈ 1 分钟

Day13 AcWing 93. 递归实现组合型枚举
Day13 LeetCode 90. 子集 II

输入、输出

93. 递归实现组合型枚举

输入样例：

1
5 3

输出样例：

1
2
3
4
5
6
7
8
9
10
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

90. 子集 II

输入样例：

1
nums = [1,2,2]

输出样例：

1
[[],[1],[1,2],[1,2,2],[2],[2,2]]

思路

  1. 递归
  2. 回溯

代码

93. 递归实现组合型枚举
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 <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 30;

int n, m;
int path[N];

void dfs(int u, int start)
{
    if (u > m)
    {
        for (int i = 1; i <= m; i ++ )
            printf("%d ", path[i]);
        puts("");
    }
    else
    {
        for (int i = start; i <= n; i ++ )
        {
            path[u] = i;
            dfs(u + 1, i + 1);
            path[u] = 0;
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    dfs(1, 1);
    return 0;
}
90. 子集 II
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
class Solution {
public:
    unordered_map<int, int> cnt;
    vector<vector<int> > ans;
    vector<int> path;

    vector<vector<int>> subsetsWithDup(vector<int> &nums) {
        for(auto x: nums) cnt[x]++;
        dfs(-10);
        return ans;
    }

    void dfs(int u)
    {
        if(u>10) ans.push_back(path);
        else
        {
            for(int i=0;i< cnt[u]+1;i++)
            {
                dfs(u+1);
                path.push_back(u);
            }
            for(int i=0;i<cnt[u]+1;i++) path.pop_back();
        }
    }
};