Подсчитайте способы поставить «+» и «-» перед элементами массива, чтобы получить сумму K

Дан массив A[] , состоящий из N неотрицательных целых чисел, и целое число K , задача состоит в том, чтобы найти количество способов, которыми операторы «+» и «-» могут быть размещены перед элементами массива A[] таким образом, что сумма массива становится K .

Примеры:

Input: A[] = {1, 1, 2, 3}, N = 4, K = 1
Output: 3
Explanation: Three possible ways are:

1. + 1 + 1 + 2 – 3 = 1
2. + 1 – 1 – 2 + 3 = 1
3. – 1 + 1 – 1 + 3 = 1

Input: A[] = {1, 1, 1, 1, 1}, N = 5, K = 3
Output: 5

Подход: Задача может быть решена на основе следующих наблюдений:

1. Сохраните сумму элементов, имеющих «+» перед этим элементом и «-» перед этим элементом в переменных, скажем, P1 и P2 , чтобы сумма массива стала K.
2. Сохраните общую сумму массива A[] в переменной, скажем, K .
3. Следовательно, возникают следующие уравнения:
   1. P1 + P2 = сумма
   2. П1 – П2 = К
      
4. Решение приведенных выше уравнений дает P1 = (сумма + K) / 2 .
5. Поэтому задача трансформировалась в нахождение количества подмножеств с суммой P1.
6. Если элемент A равен 0 , оба оператора '+' и '-' работают в допустимых сочетаниях, таким образом, 0 можно безопасно игнорировать и вычислять отдельно.

Следовательно, проблема может быть решена с помощью динамического программирования. Выполните следующие шаги, чтобы решить проблему:

1. Вычислите и сохраните сумму элементов массива A[] и количество нулей в A[] в переменных sum и c соответственно.
2. Если K больше суммы или (сумма + K) нечетно, вернуть 0 .
3. Добавьте K к сумме и разделите ее на 2, т.е. сумма = (сумма + K) / 2 , что является требуемой суммой. Найдите количество подмножеств, равных этой сумме.
4. Создайте массив 2D dp размерностей N*sum . где dp[i][j] представляет количество подмножеств до i-1 , которые имеют сумму j .
5. Базовые случаи, которые необходимо учитывать, следующие:
   1. dp[0][i] = 0 , для 0 <= i <= sum , так как элементы массива A[] не учитывались
   2. dp[i][0] = 1 , для 0 <= i <= N , так как всегда возможно получение суммы 0 .
6. Итерируйте от 1 до N и для каждого текущего индекса i выполните следующие операции:
   1. Итерируйте от 1 до суммы и для каждого текущего индекса j выполните следующие переходы:
      1. Если A[i – 1] меньше j и A[i – 1] не равно 0 , установите dp[i][j] = dp[i – 1][j] + dp[i – 1][ j – A[i – 1]].
      2. В противном случае скопируйте предыдущее состояние, т.е. dp[i][j] = dp[i – 1][j].
7. Наконец, верните произведение dp[N][sum] и 2 ^c (для учета нулей), т.е. dp[N][sum]*2 ^c .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N * сумма)
Вспомогательное пространство: O(N * сумма)