Как посчитать число возможных комбинаций для массива, сумма элементов которого равна заданному числу

Можно посчитать.

Обозначим в вашем случае это число представлений как R(n,m) — представлений числа n из m частей.

Очевидно, что R(n,1) = 1 — само число n.

Не менее очевидно (если подумать), что

R(n,m) = R(n,m-1) + R(n-1,m-1) + R(n-2,m-1) + ... + R(0,m-1)

(Количество представлений, начинающихся с 0, с 1, с ..., с n).

Остается только считать...

unsigned long long R(int n, int m)
{
    if (m == 1) return 1;
    unsigned long long s = 0;
    for(int i = 0; i <= n; ++i) s += R(n-i,m-1);
    return s;
}

Правда, в таком виде считать будет ну очень долго... Но если применить мемоизацию - то весьма быстро :)

Я использовал boost для длинной арифметики и посчитал

R(64,32) = 9900582591005555469968805

R(256,128) = 203602220919700916657542151465697367795896339716832636330737569006349813543209142455967648120505774630309

Это просто чтоб было понятно, что без длинной арифметики не обойтись...

А можно и просто формулу записать:

С учетом исправления от Stanislav Volodarskiy код выглядит как

unsigned long long R(int n, int m)
{
    if (m == 1) return 1;
    unsigned long long s = 0;
    for(int i = 0; i <= min(n,255); ++i) s += R(n-i,m-1);
    return s;
}

Во избежание переполнения стека можно использовать восходящее ДП, примерно так (с Boost'ом):

#include <vector>
#include <iostream>
#include <boost/multiprecision/cpp_int.hpp>
using large = boost::multiprecision::cpp_int;
//using large = long long int;

using namespace std;

large R(unsigned int n, unsigned int m)
{
    vector<vector<large>> R(2, vector<large>(n+1));
    for(unsigned int i = 0; i <= n; ++i)
        R[0][i] = 0;
    R[0][0] = 1;

    for(unsigned int k = 1; k <= m; ++k)
    {
        for(unsigned int l = 0; l <= n; ++l)
        {
            R[k%2][l] = 0;
            for(unsigned int j = 0; j <= min(l,255u); ++j)
                R[k%2][l] += R[(k-1)%2][l-j];
        }
    }
    return R[m%2][n];
}

int main(int argc, char * argv[])
{
    cout << R(8,2) << endl;
    cout << R(8,3) << endl;
    cout << R(8192,64) << endl;
    cout << R(32768,256) << endl;
}

Те же результаты, что и у Stanislav Volodarskiy, получились суммарно за примерно 41с.

f(n, s) - число комбинаций n байт с суммой s.

f(n = 0, s =  0) = 1 # ровно один пустой массив с нулевой суммой
f(n = 0, s != 0) = 0 # нет пустых массивов с ненулевой суммой
f(n    , s <  0) = 0 # нет массивов с отрицательными суммами

# перебираем значения первого байта [0, 255] 
f(n, s) = f(n - 1, s) + f(n - 1, s - 1) + ... + f(n - 1, s - 255)

Последняя функция позволяет вычислить комбинации из n байт если известны комбинации для массивов без одного байта.

import java.math.BigInteger;

public class ByteArrayCounter {
    public static void main(String[] args) {
        int n = Integer.parseInt(args[0]);
        int s = Integer.parseInt(args[1]);
        System.out.println(count(n, s));
    }

    private static class Slice {
        private final int min_s;
        private final int max_s;
        private final BigInteger[] values;

        public Slice(int min_s, int max_s) {
            this.min_s = min_s;
            this.max_s = max_s;
            values = new BigInteger[max_s - min_s + 1];
        }

        public void put(int s, BigInteger value) {
            values[s - min_s] = value;
        }

        public BigInteger get(int s) {
            return values[Math.min(Math.max(s, min_s), max_s) - min_s];
        }
    }

    public static BigInteger count(int n, int target) {
        Slice prev = new Slice(0, 1);
        prev.put(0, BigInteger.ZERO); 
        prev.put(1, BigInteger.ONE); 

        for (int k = 1; k <= n; ++k) {
            int min_s = Math.max(0, target - (n - k) * 255);
            int max_s = Math.min(target, 255 * k);
            Slice curr = new Slice(min_s, max_s + 1);

            BigInteger sum = BigInteger.ZERO;
            for (int s = min_s; s <= max_s; ++s) {
                curr.put(s, sum);
                sum = sum.add(prev.get(s + 1).subtract(prev.get(s - 255)));
            }
            curr.put(max_s + 1, sum);
            prev = curr;
        }
        return prev.get(target + 1).subtract(prev.get(target));
    }
}

$ javac ByteArrayCounter.java

$ java ByteArrayCounter 2 8
9

$ java ByteArrayCounter 3 8
45

$ time java ByteArrayCounter 64 8160
9026336239045655001244965373296023105444920683088436131635804094077226110833295302707931885726706613257712644527244047907893777368834358449320418590464

real  0m0.111s
user  0m0.184s
sys   0m0.024s

$ time java ByteArrayCounter 256 32640
10897341114494371171102390425834798313841110593688859167594391356773737286992667718077704666558643734411890674253371174888965746439841827767400663712320877526614540552636601516778532517789699888302122831088753711642851681086577235455694712347258199556937123993807637939401303229753741602912013795360270232412995260890580055145445625454765347778704296531450402318403895128351074924613544802496131603672001322229357896828953535411931321247887018779521144847634566656530685152627684892824858975836784160381128622874905657615087142114702175103656568693367179095144577756562635961430518965203949176730432548612295032576

real  0m0.900s
user  0m0.940s
sys   0m0.168s