Количество разложений числа на различные слагаемые Опции

[klem4]

Hi all!

Имею проблему с решением задачи, то есть решение есть, но за непримемлемое время(необходимо уложиться в 1с).
И так, имеем последовательность числел от 1 до N (1<=N<=39).
Например при N = 4 это будет последовательность {1,2,3,4}

Необходимо: найти количество разбиений данного множества на две части(непустые), такие что сумма их элементов одинакова.

То есть при n = 3, ответ будет 1, так как {1,2,3} == {3} и {2,1}
при n = 7, ответ будет 4, так как {1,2,3,4,5,6,7} ==
{1, 6, 7} и {2, 3, 4, 5}
{2, 5, 7} и {1, 3, 4, 6}
{3, 4, 7} и {1, 2, 5, 6}
{1, 2, 4, 7} и {3, 5, 6}

Очевидно, если сумма всех элементов множества нечетная, то ответ - 0, так как сумма его элементов не делится на 2 и соответственно не может быть разделена на 2 равные части.

Где-то полчаса потратил на поиск по форуму, похожие задачки были, но все не совсем то что надо.


Я пока родил следующее решение(перебор с возвратом), но при n > 22 оно сильно тормозит, ибо количество итераций в рекурсии сильно растет.

Буду признателен за наставление на путь истенный, несложная вроде задача, хочется научиться ее решать
Код на python, не обессудьте Паскаль уже напроч забыл ...

Кода кот наплакал, если нужны пояснения, добавлю.

Спойлер (Показать/Скрыть)

Код

#!/usr/bin/python


import sys
COUNT = 0


def sequence_sum(first, last):
    return int((first + last) / 2.0 * (last - first + 1))


def element_ok(curr_sum, need_sum, element):
    return curr_sum + element <= need_sum


def sequence_ok(from_element, curr_sum, need_sum):
    seq_sum = sequence_sum(1, from_element)
    return curr_sum + seq_sum >= need_sum


def solution(curr_el, curr_sum, need_sum, size):
    if curr_sum == need_sum:
        globals()['COUNT'] += 1
    else:
        digit = curr_el - 1
        while digit:
            if not sequence_ok(digit, curr_sum, need_sum):
                break
            else:
                if element_ok(curr_sum, need_sum, digit):
                    solution(digit, curr_sum + digit, need_sum, size)
            digit -= 1


if __name__ == '__main__':

    seq_size = int(sys.argv[1] if len(sys.argv) > 1 else 3)
    full_sum = sequence_sum(1, seq_size)
    half_sum = int(full_sum / 2.0)

    if not full_sum % 2:
        solution(seq_size, seq_size, half_sum, seq_size)

    print COUNT