"""
Проверяет условия завершения рекурсии или продолжает её.

pos      -- текущее количество шагов (глубина рекурсии),
seq      -- текущая цепочка значений,
n        -- целевое значение,
minlen   -- максимальная разрешённая глубина (минимально найденная длина до этого момента).

Возвращает кортеж из:
(minimal_length_found, number_of_ways_with_that_length)
"""
function checksequence(pos, seq, n, minlen)
    # Если мы уже превысили известный минимум – дальше не стоит проверять
    pos > minlen || seq[1] > n ? (minlen, 0) :

    # Если первое значение стало больше N – цепочка не годится
    seq[1] == n ? (pos, 1) : # Мы достигли цели! Возвращаем кол-во шагов и одну найденную цепочку

    # Если ещё не достигли максимума, но можно продолжать перебирать:
    pos < minlen ? trypermutation(0, pos, seq, n, minlen) : (minlen, 0) # Иначе всё равно перешагнули
end

"""
trypermutation(i, pos, seq, n, minlen) 

i          -- индекс последнего элемента, который может быть слагаемым,
pos        -- сколько элементов есть в текущей цепочке (длина цепочки),
seq        -- сама цепочка чисел,
n          -- целевое (искомое) число,
minlen     -- текущая лучшая найденная длина цепочки.

Возвращает пару (лучшая_длина, число способов получить эту длину).
"""
function trypermutation(i, pos, seq, n, minlen)
    if i > pos
        return minlen, 0 # Ничего нового не нашлось – просто возвращаем минимум
    end
    
    new_seq = deepcopy(seq) # Создаём копию цепочки
    pushfirst!(new_seq, seq[1] + seq[i+1]) # Добавляем новое число в начало (слева): a[j] = a[1]+a[i+1]

    res1 = checksequence(pos + 1, new_seq, n, minlen) # Проверяем полученную цепочку дальше

    res2 = trypermutation(i + 1, pos, seq, n, res1[1]) # Пробуем другой вариант i -> i+1

    # Выбираем наилучший результат:
    if res2[1] < res1[1]
        return res2
    elseif res2[1] == res1[1]
        return res2[1], res1[2] + res2[2] # Если равно — складываем количества путей
    else
        error("Результат с большим i меньше результата меньшей i – логически ошибочно!")
    end
end

for num in [7, 14, 21, 29, 32, 42, 64, 47, 79, 191, 382, 379]
    (minlen, nchains) = trypermutation(0, 0, [1], num, 12) # Стартовая цепочка — [1]; максимальная допустимая длина — 12
    println("N = ", num)
    println("Минимальная длина цепочек: L(n) = ", minlen)
    println("Количество цепочек такой длины (число Брауэра): ", nchains)
end