第一次写题解,表达不清楚还请体谅
在1的基础上做些修改,
对于重复的数字,只考虑第一个.
当包含第一个重复数字的所有情况考虑完后,以后重复的数字就直接跳过不选。
当第n个数考虑完后,就可以输出了,速度30ms
C++ 代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, a[50], vis[50];
int m;
vector<int> ans;
void dfs(int k)
{
if( ans.size() > m || ans.size() + (n - k) < m ) //只要M个数,大于了M马上剪枝
return;
if( k > 0 && a[k] == a[k - 1] && vis[k - 1] == 0) //如上所述
{
dfs(k +1);
return;
}
if( k == n )
{
for(int i=0;i<ans.size();i++)
cout << ans[i] << " ";
cout << endl;
return;
}
ans.push_back(a[k]);
vis[k] = 1;
dfs(k + 1); //选
vis[k] = 0;
ans.pop_back();
dfs(k +1); //不选
}
int main()
{
cin>>n>>m;
for(int i = 0; i < n; i++ )
cin >> a[i];
sort(a,a+n);
dfs(0);
return 0;
}
vis[k - 1] == 0 怎么理解