幸运号码（计算具有指定数字总和的幸运号码数量）

Question

这里是问题。

给定一个数字 1 ≤ N ≤ 50。每个票据都有它的2N位数。如果它的前N位数字之和等于后N位数字之和，我们称这张票为幸运票。您还知道数字中所有数字的总和。您的任务是计算具有指定数字总和的幸运票的数量。

对于输入 2 2，输出为4（0101、0110、1001、1010）。

你能帮我解决这个问题吗？最小复杂度是多少？

- Elmi Ahmadov

---

这个问题也出现在2011年伯克利编程竞赛的问题#2中。 整个问题集可以在此处找到：[f2011-contest.pdf]（http://www.cs.berkeley.edu/~hilfingr/programming-contest/f2011-contest.pdf）。 - nibot

Answer 1

如果所需的总和为s，那么每一半必须有总和s/2。现在，你需要找到f(n, s/2)：有多少个n位数字的数字之和是s/2。知道了f(n, s/2)，你可以用一行代码得出答案（试着自己想一下）。

至于如何计算f(n, m)：这是标准的DP。你有递归公式，如f(n, m) = f(n-1, m) + f(n-1, m-1) + f(n-1, m-2) + ... + f(n-1, m-9)。这里，0, 1, 2, .. 9是给定数字的最后一位的所有可能选项。如果最后一位是k，那么剩下的就是数字之和为m - k的长度为(n-1)的数字。

希望这能帮到你。

附言：根据问题的限制，你需要一些长算术才能通过它。

- Nikita Rybak

Answer 2

private static boolean isLucky(int n) {

    int sum1 = 0;
    int sum2 =0;
    String s = String.valueOf(n);
    System.out.println("After Conversion in String= " + s);
    for (int i = 0; i < (s.length()) / 2; i++) {
        System.out.println("half string === " + s.charAt(i));
        sum1 = sum1 + Character.getNumericValue(s.charAt(i));
    }
    System.out.println("half sum === " + sum1);
    for(int j=(s.length()) / 2 ; j< s.length();j++){
        System.out.println("half string === " + s.charAt(j));
        sum2 = sum2 + Character.getNumericValue(s.charAt(j));
    }
    System.out.println("another half sum === " + sum2);
    if(sum1 == sum2){
        return true;
    }
    return false;
}

- Binal Parekh