данный массив найти все комбинации элементов, которые дают сумму

Question

Мне задали следующий вопрос в интервью. Хотя я ответил на это с использованием n-арного дерева, мне сказали, что это не «достаточно хорошо». Итак, мне интересно, каково оптимальное решение для этого.

Входной сигнал: массив целых чисел: [2, 3, 7], а сумма: 10

Выход: все комбинации элементов массива, которые складываются в сумме (например, 2 + 2 + 2 + 2 + 2, 2 + 2 + 3 + 3, 3 + 7 и т.д.)

Благодаря, Т

Answer 1

Эта проблема может быть решена с помощью dynamic programming. У вас есть двумерный dp. Допустим, вы делаете dp в массиве с именем mem. mem [i] [j] сохранит количество способов достижения суммы i с элементами индексов j, j + 1... n (здесь n - это размер массива).

У вас есть следующее отношение: mem[i][j] = mem[i][j+1] + mem[i - a[j]][j+1] (конечно, вы должны проверить, не не менее a[j]). И теперь вы можете найти количество способов, которыми вы можете достичь суммы S, получив значение mem[S][j]. восстановление решений не очень сложно, если у вас есть массив. Я предлагаю вам попробовать сделать это самостоятельно и написать комментарий, если вы не можете понять это.