How to find the number of options for obtaining a number from a sequence of numbers?

Question

Mathematics

Given a sequence of numbers. For example: 2 9 3 6 3 8 1 10 6 7.
You need to find out how many ways you can form a number greater than 8. What is the important condition: if we have already achieved that the combination is greater than 8 (3+3+3=9) , then it is no longer possible to supplement the combination with new numbers (3+3+3+5 is impossible, because 3+3+3 is already > 8).
The correct answer is 42, but I can't figure out how to achieve it.
I understand that you can iterate over the sequence (2+9, 2+3+3, 2+...) and see if it's greater than 8 or not, but that's too long. I already googled combinatorics, but I did not find a solution. So I turned here.
Tell me the formula or push in the right direction.

Answer 1

Generate all combinations , summarize, compare.
He googled, it's called...

Answer 2

It suggests sorting in ascending order, then a recursive enumeration with pruning by criterion.
Sorting

функция перебор(numbers, result, summ) {
    пока numbers не пуст {
        current = numbers[0]; // первое число
        numbers = numbers[1..]; // остаток массива
        если summ+current > 8 
            вывести result, current;
        иначе
            перебор(numbers, [result | current], summ+current);
    }
}
перебор([1 | 2 | 3 | 3 | 6 | 6 | 7 | 8 | 9 | 10], [], 0);

Answer 3

Yes, the task has nothing to do with what you wrote at the beginning. It is necessary to find the number of subsegments - that is, fragments of the sequence without gaps. They don't have the restriction "you can't lengthen the segment if the sum has reached M+1" - they only say that you can not lengthen it. The fact that we "use the modulus" does not mean that we need to take the sum of the moduli - otherwise the answer would be about 50. Probably, it means that the modulus of the sum must be greater than M (this cannot be understood from the example, there is no segment with the sum less than -8).
I can say that the task is not an easy one. It can't be solved by brute force (requires N^2/2 comparisons, you can't do it in a second).
I would do so. Take an array of partial sums (0, a0, a0+a1, ...). Then make log_2(N) copies of this array (numbered by index k from 1 to log_2(N)), and sort the segments of length 2^k in each of them. For an array from the task, it would look like this:
S0=S[0]=[0,-2,7,10,16,19,27,26,36,30,37]
S[1]=[-2,0 , 7.10, 16.19, 26.27, 30.36, 37]
S[2]=[-2.0.7.10, 16.19.26.27, 30.36.37]
S[ 3]=[-2,0,7,10,16,19,26,27, 30,36,37]
Unfortunately, the arrays S[1],S[2],S[3] turned out to be the same - this is because that there are few negative numbers in the example.
Having such arrays, you can easily answer the question "how many numbers in the array fragment S0[k+1]..S0[N] do not belong to the range S0[k]-M .. S0[k]+M" (time - log( M)^2). The sum of such answers for all k from 0 to M-1 will give the answer to the problem. Total time - M*log(M)^2.
UPD. It would be better if they wrote the condition in English. It would not be so ashamed of the wording.

Answer 4

Due to the fact that there were misunderstandings of the conditions, I post the original (it should have been done right away)