Подсчитайте способы разбить массив на два подмножества, разница между их суммой которых равна K

Имея массив A[] размера N и целое число diff , задача состоит в том, чтобы подсчитать количество способов разбить массив на два подмножества ( возможно непустое подмножество ) так, что разница между их суммами равна diff .

Примеры:

Input: A[] = {1, 1, 2, 3}, diff = 1  
Output: 3  
Explanation: All possible combinations are as follows: 

• {1, 1, 2} and {3}
• {1, 3} and {1, 2}
• {1, 2} and {1, 3}

All partitions have difference between their sums equal to 1. Therefore, the count of ways is 3.

Input: A[] = {1, 6, 11, 5}, diff=1
Output: 2

Наивный подход: самый простой подход к решению проблемы основан на следующих наблюдениях:

Let the sum of elements in the partition subsets S1 and S2 be sum1 and sum2 respectively.
Let sum of the array A[] be X. 
Given, sum1 – sum2 = diff – (1)
Also, sum1 + sum2 = X – (2)

From equations (1) and (2), 
sum1 = (X + diff)/2

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

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

Эффективный подход. Чтобы оптимизировать описанный выше подход, идея состоит в том, чтобы использовать динамическое программирование. Инициализируйте таблицу dp[][] размера N*X , где dp[i][C] хранит количество подмножеств подмассива A[i…N-1] таким образом, что их сумма равна C . Таким образом, повторение очень тривиально, поскольку есть только два варианта выбора, т. е. либо рассматривать i ^-й элемент в подмножестве, либо нет. Таким образом, рекуррентное соотношение будет:

dp[i][C] = dp[i – 1][C – A[i]] + dp[i-1][C]

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

Временная сложность: O(S*N), где S = сумма элементов массива + K/2 .
Вспомогательное пространство: O(S*N)