Алгоритм для нахождения всех различных сумм из списка чисел

ProgramBox

Алгоритм для нахождения всех различных сумм из списка чисел

Post author:admin
Запись опубликована:9 февраля, 2023
Post category:Вопросы по программированию

#java #algorithm #data-structures #combinations #permutation

#java #алгоритм #структуры данных #комбинации #перестановка

Вопрос:

Пример ввода:

 4 6 4 3 2 2 1 1

Первое число = общее число, T (T < 1000)

Второе число = количество чисел, S (S <= 12)

Следующие S чисел = значения чисел (каждое значение <100). (Может произойти повторение, ввод вводится в порядке возрастания)

Моя задача — найти все «различные суммы», используя числа из списка, которые в сумме равны T.

Итак, пример вывода для этого ввода будет:

Моя мысль заключалась в том, чтобы просмотреть список 1 на 1 и найти все комбинации числа с другим числом, вплоть до размера списка чисел — # уже оцененных чисел. Вы создаете список из каждой комбинации и добавляете список в хэш-набор списков (хэш-набор для предотвращения дублирования).

Итак, вы бы проверили все 1, 2, 3, 4, 5, и комбинации 6-го размера, чтобы сначала использовать 4, а затем все 1, 2, 3, 4, 5- комбинации размера, чтобы перейти к 3, игнорируя 4, затем все комбинации размера 1, 2, 3, 4.чтобы перейти к 2, игнорируя 4 и 3

и т.д.

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

1. Рекурсия будет работать при условии, что S она достаточно мала. Каковы ограничения на T , S , и значения?

2. Каковы ограничения на T и S это действительно важно для выбора алгоритма. Также, если это вопрос из конкурса по программированию, можете ли вы предоставить ссылку для проверки наших ответов?

3. Ограничения довольно малы, T < 1000, целых чисел будет не более 12, и все целые числа меньше 100.

4. В этом случае даже O(2^n) сложность приемлема, современному процессору потребуется не более миллисекунды, чтобы перебрать результат.

Ответ №1:

Вы должны попробовать рекурсивное решение. В основном вам просто нужно работать с идеей, что для каждого числа вы можете либо включить его в свою сумму, либо нет. Это означает, что вы создаете степенной набор своих чисел и получите O(2^N) решение.

Кратко в псевдокоде:

 def get_all_sums(arr, target):

    result = []

    def helper(index, current_arr, current_sum):

        # once you've gone over the arr you can return. If all your numbers are positive
        # you can also return early if the current_sum > target
        if index == len(arr): return

        # solution found - add it to the result
        if current_sum == target: result.append(current_arr)

        # include the current index
        helper(index   1, current_arr   [arr[index]], current_sum   arr[index])

        # don't include the current index
        helper(index   1, current_arr, current_sum)

    helper(0, [], 0)

    # sort and hash to get rid of duplicates; return a set
    return {tuple(sorted(i) for i in result)}

1. Можете ли вы объяснить, что такое current_arr и как вы используете параметры для dfs? Например, как выглядит ваша реализация dfs?

2. @AndIAm извините, это не должно было быть helper dfs

3. Это не работает … есть ли у вас какое-либо правильное решение.

Ответ №2:

Ответ можно найти с помощью простой рекурсии, которую я продемонстрирую на примере из вопроса.

На первом уровне рекурсии решаемая проблема

 target=4 count=6 allowed={4,3,2,2,1,1} chosen={}

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

 target=0 size=5 allowed={3,2,2,1,1} chosen={4}
target=1 size=4 allowed={2,2,1,1} chosen={3}
target=2 size=3 allowed={2,1,1} chosen={2}
target=3 size=1 allowed={1} chosen={1}

Ключевым моментом здесь является то, что массив допустимых значений уменьшается на каждом уровне рекурсии. Могут использоваться только те значения, которые следуют за выбранным значением. Так, например, когда первый уровень рекурсии выбирает значение 3, тогда допускаются только значения, меньшие 3. В случае дубликатов выбирается первый дубликат, а разрешенные значения ограничены оставшимися дубликатами и любыми меньшими значениями.

На втором уровне рекурсии, когда параметры

 target=0 size=5 allowed={3,2,2,1,1} chosen={4}

Это успешный базовый вариант: target равно 0. В этом случае добавьте {4} в список вывода, поскольку это решение.

На втором уровне рекурсии, когда параметры

 target=1 size=4 allowed={2,2,1,1} chosen={3}

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

 target=0 size=1 allowed={1} chosen={3,1}

Это опять же базовый вариант, поэтому третий уровень рекурсии добавит {3,1} к результату.

На втором уровне рекурсии, когда параметры

 target=2 size=3 allowed={2,1,1} chosen={2}

будет два рекурсивных вызова

 target=0 size=2 allowed={1,1} chosen={2,2}
target=1 size=1 allowed={1} chosen={2,1}

Первый из них является базовым, поэтому добавьте {2,2} к результату. Другой рекурсивный вызов в конечном итоге добавит {2,1,1} к результату.

На втором уровне рекурсии, когда параметры

 target=3 size=1 allowed={1} chosen={1}

существует один рекурсивный вызов

 target=2 size=0 allowed={} chosen={1,1}

Это неудачный базовый вариант: target ненулевой и size равен 0.

Обратите внимание, что когда задача решается таким образом, генерируются только уникальные решения, поэтому нет необходимости удалять повторяющиеся решения.

Также обратите внимание, что максимальная глубина рекурсии определяется S , поэтому важно, чтобы S она была ограничена достаточно малым числом ( S <= 12 квалифицируется как достаточно малое).