专栏首页ypw回溯法求组合问题

回溯法求组合问题

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


bool ok(int get[],int k){
  for(int i=0;i<k;i++)
    if(get[i]>=get[k])
     return false;
return true;
}

void print(int a[],int len){//用与打印 
  for(int i=0;i<len;i++)
    cout<<a[i]<<" ";
      cout<<endl;
}

int main(){
int sum=0;int n,m;
//回溯法从n个数字里面选取m个出来
cout<<"输入总数"<<endl;cin>>n;//读入整数 
int num[n];
cout<<"分别输入这"<<n<<"个数字"<<endl;

for(int i=0;i<n;i++)cin>>num[i];

sort(num,num+n);

cout<<"要取多少个数字组合在一起?"<<endl;
cin>>m;

int get5[m];//需要多少个数字形成组合
 
for(int i=0;i<m;i++) 
  get5[i]=-1;
  
 int k=0;
 int c[m];
for(int i=0;i<m;i++)
    c[i]=0;

     while(k>=0){
     while(c[k]<n){
     get5[k]=num[c[k]++];
if(ok(get5,k)&&k==m-1)//得到一个完整组合 
{
sum++;
}
else if(ok(get5,k)&&k<m-1)k++;//得到部分解,继续往下走 
}
get5[k]==-1;
c[k]=0;
k--;
} 
cout<<"共有"<<sum<<"个组合"<<endl;

} 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 口算训练 HDU - 6287

    小Q非常喜欢数学,但是他的口算能力非常弱。因此他找到了小T,给了小T一个长度为n的正整数序列a1,a2,…,an,要求小T抛出m个问题以训练他的口算能力。

    用户7727433
  • 迷宫的最短路径

    题意:给定一个大小为N * M的迷宫,迷宫由通道与墙壁组成,每一步可以向邻接的上下左右四格的通道移动。请求出从起点到终点所需要的最下步数。

    用户7727433
  • 用归并排序求逆序对数(包括归并排序算法实现及代码)

    那么我们很容易想到这个题有一种O(n*n)的暴力解法,但这不是我们所需要的,所以,要想归并排序来实现求逆序对数,那么首先我们要了解并掌握归并排序算法。

    用户7727433
  • Java中实现找到两个数组交集的2种方法,开发实用

    1、用HashSet实现的解决方法 实例代码如下: public int[] intersection(int[] nums1, int[] nums2) { ...

    用户1289394
  • C++中动态申请数组

    动态申请一维数组 申请使用new,释放使用delete[] 可以通过数组名[下标]和*(数组名+下标)的方式访问数组

    卡尔曼和玻尔兹曼谁曼
  • 1061 判断题 (15 分)

    可爱见见
  • 图像处理卷积算法实现

      今天心血来潮,想把传统的卷积算法实现一份不采用各种加速方式,仅优化算法逻辑的纯净版本。 写完发现性能还可以,特发出来分享之,若有博友在此基础上,进行了再次优...

    cpuimage
  • 排序算法——一篇文章搞懂常用的排序算法

    排序:所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。 稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记...

    海盗船长
  • 常见指针定义解读

    最近做的C/C++技术面试比较多,发现了一些共同的问题,对于如下所示的指针认识,多数面试者都答错了,作为过来人,这种情况还可以理解的,放在一起确实有些复杂。 ...

    一见
  • leetcode题解 | 78. 子集

    这个题目很容易想到使用DFS的方式来解决,因为组合的题容易产生转移方程,这样也是没有什么问题的。

    ACM算法日常

扫码关注云+社区

领取腾讯云代金券