题目描述

有n个包含重复数字的序列，每次可以取的个数任意。

算法1

因此分为取还是不取情况，对于第n个坑位来说，如果之前已经有第n位的重复数字出现，那么含第n位数字的情取第n位。

时间复杂度

C++ 代码

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 20;
int a[N];
vector<int> b;
int n;

void dfs(int u) {
    for(int i = 0; i < b.size(); i++) 
        cout << b[i] << " ";
    puts("");

    for(int i = u; i < n; i++) {
        if(i != u && a[i - 1] == a[i]) continue;
        b.push_back(a[i]);
        dfs(i + 1);
        b.pop_back();
    }
    return;
}

int main() {
    cin >> n;
    for(int i = 0, t; i < n; i++)   cin>>a[i];
    sort(a, a+n);
    dfs(0);
    return 0;
}

算法2

有n个包含重复数字的序列，每次可以取的个数任意，因此分为取还是不取情况，对于第n个坑位来说，如果之前已经有第n位的重复数字出现，那么含第n位数字的情况已经被取完了，因此不取第n位。

C++ 代码

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 20;
int a[N];
bool st[N];
vector<int> b;
int n;

void dfs(int u) {
    if(u==n)
    {
       for(auto c:b) 
            cout << c << " ";
        puts(""); 
        return ;
    }
    dfs(u + 1);    //不选
    if(u>0 && a[u]==a[u-1] && !st[u-1])  return ; //选的时候考虑不可以取到的情况
    b.push_back(a[u]);
    st[u]=true;
    dfs(u + 1);
    b.pop_back();
    st[u]=false;
}

int main() {
    cin >> n;
    for(int i = 0; i < n; i++)   cin>>a[i];
    sort(a, a+n);
    dfs(0);
    return 0;
}