Java 解法, 执行用时: 481ms, 内存消耗: 12932K, 提交时间: 2023-07-23 10:41:10

import java.io.*;
import java.util.*;

public class Main {

    static int ans = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        List<Integer> set = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            set.add(Integer.parseInt(br.readLine()));
        }
        getSubsets(set);

        bw.write(ans + "\n");
        bw.flush();
        bw.close();
    }
    public static void getSubsets(List<Integer> set) {

        int n = set.size();

        for (int i = 0; i < (1<<n); i++) {
//            List<Integer> subset = new ArrayList<>();
            int[] digitSum = new int[10];
            int count = 0;
            for (int j = 0; j < n; j++) {
                if ((i & (1<<j)) > 0) {
//                    subset.add(set.get(j));
                    count++;
                    int next = set.get(j);
                    for (int k = 9; k >= 0; k--) {
                        digitSum[k] += next%10;
                        next /= 10;
                    }
                }
            }

            boolean noCarry = true;
            for (int j = 0; j < 10; j++) {
                if (digitSum[j]>9) {
                    noCarry = false;
                    break;
                }
            }
            if (noCarry) {
//                System.out.println(subset);
                ans = Math.max(ans, count);
            }

        }

    }

}

C++14(g++5.4) 解法, 执行用时: 18ms, 内存消耗: 492K, 提交时间: 2020-09-20 19:18:32

#include <bits/stdc++.h>
using namespace std;
int n,maxx;
int a[25];
void dfs(int pos,int sum,int num)
{
    if(pos==n+1){
        maxx=max(maxx,num);
        return;
    }
    int t1=sum,t2=a[pos];
    int f=1;
    while(t1>0&&t2>0){
        int aa=t1%10,bb=t2%10;
        if(aa+bb>=10){
            f=0;
            break;
        }
        t1/=10,t2/=10;
    }
    if(f==1) dfs(pos+1,sum+a[pos],num+1);
    dfs(pos+1,sum,num);
}
int main()
{
    int k,m;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    dfs(1,0,0);
    cout<<maxx<<endl;
}

C++11(clang++ 3.9) 解法, 执行用时: 14ms, 内存消耗: 376K, 提交时间: 2020-09-19 13:27:32

#include<bits/stdc++.h>
using namespace std;
int n,maxx;
int a[25];
void dfs(int pos,int sum,int num)
{
	if(pos==n+1)
	{
		maxx=max(maxx,num);
		return;
	}
	int t1=sum,t2=a[pos];
	int f=1;
	while(t1>0&&t2>0)
	{
		int aa=t1%10,bb=t2%10;
		if(aa+bb>=10)
		{
			f=0;
			break;
		}
		t1/=10,t2/=10;
	}
	if(f==1)
	dfs(pos+1,sum+a[pos],num+1);
	dfs(pos+1,sum,num);
}
int main()
{
	int k,m;
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	dfs(1,0,0);
	cout<<maxx<<endl;
}