数字分组求偶数和

问题描述

小M面对一组从 1 到 9 的数字，这些数字被分成多个小组，并从每个小组中选择一个数字组成一个新的数。目标是使得这个新数的各位数字之和为偶数。任务是计算出有多少种不同的分组和选择方法可以达到这一目标。

• numbers: 一个由多个整数字符串组成的列表，每个字符串可以视为一个数字组。小M需要从每个数字组中选择一个数字。

例如对于[123, 456, 789]，14个符合条件的数为：147 149 158 167 169 248 257 259 268 347 349 358 367 369。

测试样例

样例1：

输入：numbers = [123, 456, 789]
输出：14

样例2：

输入：numbers = [123456789]
输出：4

样例3：

输入：numbers = [14329, 7568]
输出：10

思路

1.用一个二维动态数组vector<vector<int>>去存每一个数的每一位

2.遍历每一个数的每一位，进行增加，每次到最后就判断。（这里用递归的方式进行搜索可以解决我们这个需求）如图所示：

代码

#include<bits/stdc++.h>
using namespace std;
void comb(vector<vector<int>>& groups,int index,int currentSum,int& cnt){
    if(index-1==groups.size()-1){//因为最后一次下标+1会等于这个数组的大小
        if(currentSum%2==0) cnt++;
        return;
    }
    for(int num:groups[index]){//遍历每一种可能
        comb(groups,index+1,currentSum+num,cnt);
    }
}
int solution(vector<int> numbers) {
    vector<vector<int>> groups;//用一个二维动态数组存起来
    for(int num:numbers){//遍历当中的每一个数
        vector<int> tmp;//每一个动态数组存每个数的每一位
        while(num>0){
            tmp.push_back(num%10);//这样子会从个位开始存储
            num/=10;
        }
        reverse(tmp.begin(),tmp.end());//因此得翻转一下变成高位向低位存储
        groups.push_back(tmp);//这一个动态数组存进去
    }
    int cnt=0;
    comb(groups,0,0,cnt);
    return cnt;
}

int main() {
    std::cout << (solution({123, 456, 789}) == 14) << std::endl;
    std::cout << (solution({123456789}) == 4) << std::endl;
    std::cout << (solution({14329, 7568}) == 10) << std::endl;
    return 0;
}