一组子集中的数字总和

Question

我有一个像这样的集合 S [00 01 10 11] 和一个元素 E 11。我想找出这个集合的位数之和大于等于元素的位数之和E.

的子集的个数

例如，在这种情况下，答案是 10。满足约束条件的10组为：

00 01 10 11 // Sum is 3 which is greater than 2 (sum of digits of E)
00 01 11 
00 10 11
01 10 11
00 11
01 11
10 11
11
00 01 10
01 10

以上子集所有位数之和大于等于2（E的位数之和）

我尝试了以下

public static void main(String[] args) {
    Set<String> inputSet = new HashSet<String>();
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int M = sc.nextInt();// specifies the length of the digts in the set.
    for (long i = 0 ; i < N; i++) {
        inputSet.add(sc.next());
    }
    long sum = 0;
    String E = sc.next();//
    sc.close();
    for (String str : E.split("(?!^)")) {
        sum = sum + Integer.parseInt(str);
    }
    List<Set<String>> subSets = new ArrayList<Set<String>>();
    for (String addToSets : inputSet) {
        List<Set<String>> newSets = new ArrayList<Set<String>>();
        for (Set<String> curSet : subSets) {
            Set<String> copyPlusNew = new HashSet<String>();
            copyPlusNew.addAll(curSet);
            copyPlusNew.add(addToSets);
            newSets.add(copyPlusNew);
        }
        Set<String> newValSet = new HashSet<String>();
        newValSet.add(addToSets);
        newSets.add(newValSet);
        subSets.addAll(newSets);
    }
    long sum1;
    long count = 0;
    for (Set<String> set : subSets) {
        sum1 = 0;
        for (String setEntry : set) {
            for (String s : setEntry.split("(?!^)")){
                sum1 = sum1 + Integer.parseInt(s);
            }
        }
        if (sum == sum1 || sum1 > sum)
            count = count+1;
    }
    System.out.println(count);
}

约束条件 1 <= N <= 10^5

1 <= M <= 20

上述方法不适用于 10⁵ 范围内的集合大小。请帮助为此提供一种有效的方法。谢谢！

Answer 1

解决这个问题的关键在于记住 addition is associative。所以当你添加这些数字并不重要。因此，如果我们将其简化为一个已知问题，则很容易解决这个问题。

将您的输入数组转换为 sum of digits array。也就是说，如果您的原始数组是 A，那么与结果数组 B 的关系将是：

          B[i] = sum of digits of(A[i]).

假设K是sum of digits(E)

那么你的问题就变成了

     Find number of subsets in B whose sum is <= K

这很容易。

编辑：

  public static void main(String[] args) {
    int[] A ={01,11,111};
    int B[] = new int[A.length];
    for(int i=0;i<A.length;i++){
        B[i]=getDigitSum(A[i]);
    }
     int E = 11;
    int K= getDigitSum(E);
    int N =B.length;
    Arrays.sort(B);
    int DP[][] = new int[B.length][B[B.length-1]+1];


    for (int i=0;i<N;i++) {
        DP[i][B[i]] = 1;

        if (i == 0) continue;

        for (int k=0;k<K;k++) {
            DP[i][k] += DP[i - 1][k];
        }
        for (int k=0;k<K;k++) {
            if( k + B[i] >= K) break ;
            DP[i][k + B[i]] += DP[i - 1][k];
        }
    }
    int sum=0;
    for(int i=0;i<K;i++) {
        sum = sum +DP[N-1][i];
    }
    int result = ((int)Math.pow(2,N)) - sum-1;
    System.out.println(result);

}

private static int getDigitSum(int num) {
    int sum =0;
    while(num >0){
       sum=sum+ (num%10);
        num= num/10;
    }
    return sum;
}

一组子集中的数字总和

Sum of digits in a subset of a set

java

optimization

powerset