Ответ 1
Список всех подмножеств будет оставаться O(2^N), потому что в худшем случае вам все равно придется перечислять все подмножества, кроме пустого.
Динамическое программирование может помочь вам подсчитать количество наборов с sum >= K
Вы идете снизу вверх, отслеживая, сколько подмножеств суммируется с некоторым значением из диапазона [1..K]. Такой подход будет O(N*K), который будет возможен только при малых K.
Идея с решением динамического программирования лучше всего иллюстрируется примером. Рассмотрим эту ситуацию. Предположим, вы знаете, что из всех наборов, состоящих из первых элементов i, которые вы знаете, t1 sum to 2 и t2 sum to 3. Скажем, что следующий элемент i+1 - 4. Учитывая все существующие наборы, мы можем построить все новые наборы путем добавления элемента i+1 или его исключения. Если мы оставим это, получим подмножества t1, которые суммируются с подмножествами 2 и t2, которые суммируются с 3. Если мы добавим его, мы получим подмножества t1, которые суммируются с 6 (2 + 4) и t2, которые суммируются с 7 (3 + 4). Это дает нам числа подмножеств, которые суммируются с (2,3,6,7), состоящим из первых элементов i+1. Мы продолжаем до N.
В псевдокоде это может выглядеть примерно так:
int DP[N][K];
int set[N];
//go through all elements in the set by index
for i in range[0..N-1]
//count the one element subset consisting only of set[i]
DP[i][set[i]] = 1
if (i == 0) continue;
//case 1. build and count all subsets that don't contain element set[i]
for k in range[1..K-1]
DP[i][k] += DP[i-1][k]
//case 2. build and count subsets that contain element set[i]
for k in range[0..K-1]
if k + set[i] >= K then break inner loop
DP[i][k+set[i]] += DP[i-1][k]
//result is the number of all subsets - number of subsets with sum < K
//the -1 is for the empty subset
return 2^N - sum(DP[N-1][1..K-1]) - 1