题目描述

给定一个长度为 n 的可包含重复数字的序列，从中随机选取任意多个数字，输出所有可能的选择方案

样例

输入样例：
3
1 2 2

输出样例：

1
2
1 2
2 2
1 2 2

数据范围

1≤n≤15
序列内所有元素均不大于 n。

暴力搜索(dfs)

1.由于要打印最终的结果,每一次输出的复杂度就是O(n),所以n不会太大,可以通过dfs暴力搜索来实现
2.代码整体框架还是跟之前的递归实现整数型枚举一样,看每个元素是否被选取,但是这里多了个数组用于存储结果
3.由递归搜索树可以看出,一开始的打印的方案一定是数组最后一个数,然后依次往前推,所以如果想要按字典序
就需要对数组进行逆序排序,同时打印方案的时候也需要从尾开始打印,否则逆序后按顺序打印会先打印大数
4.由于存在重复数字所以需要剪枝

C++ 代码

#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;

int state[16]={0};//结果数组
int visited[16]={0};//a数组中第i个元素是否被选
int n;
int a[16]={0};

bool cmp1(int a,int b)  
{  
    return b<a;  
}

void dfs(int u)
{   
    if(visited[u-2]==1 && a[u-1]==a[u-2] &&visited[u-1]==0)
    {
        return;
    }
    if(u>n)
    {
        for(int i=n;i>=1;i--)
            if(state[i]!=0)
                printf("%d ",a[i]);
        printf("\n");
        return;
    }
    dfs(u+1);
    visited[u]=1;       //数组a中第i个元素被选取
    state[u]=a[u];
    dfs(u+1);
    visited[u]=0;
    state[u]=0;

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