MIOJ #12 找出可能的合的组合

描述

给出一组不重复的正整数,从这组数中找出所有可能的组合使其加合等于一个目标正整数 M,如:

一组数为 1, 2, 3,目标数为 4,那么可能的加合组合为: 1, 1, 1, 1 1, 1, 2 1, 2, 1 1, 3 2, 1, 1 2, 2 3, 1 注意相同的组合数字顺序不同也算一种,所以这个例子的结果是 7 种。

输入

一组连续不重复的 N 个正整数(, 隔开,0<N<100)以及目标正整数(与数组之间用空格隔开)

输出

所有可能的加合等于目标正整数 M 的组合种数

输入样例

1,2,3 4

输出样例

7

AC代码:

#include <bits/stdc++.h>
#include<vector>
#include<stack>
#include<sstream>
using namespace std;

vector<int>a(0);
int findComb(int k){
    int sum = 0;
    for(int i = 0; i < a.size();i++){
        if(k-a[i] == 0){
            sum++;
            break;
        }
        if(k-a[i]>0){
            sum = sum +findComb(k-a[i]);
        }
        if(k-a[i]<0){
            break;
        }
    }
    return sum;
}


int main()
{
    int k ;
    int num;
    string s;
    while(cin>>s>>num)
    {
        s = s+",";
        bool flag = false;
        int b = 0;
        int j = 0;
        int k = 0;
        int cnt = 0;
        int temp = -1;
        for(int i = 0; i<s.length(); i++)
        {
            flag = false;
            b = 0;
            k = j;
            if(s[i] ==',')
            {
                while(k != i)
                {
                    b = b*10+(s[k]-48);
                    k++;
                }
                flag = true;
                // cout<<b<<endl;
                j = i+1;
            }
            if(flag == true)
            {
                a.push_back(b);
            }
        }
          sort(a.begin(),a.end());
           cout<<findComb(num)<<endl;
    }
}

 

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注