'Finding the number of subsets with sum equal to k

Can anyone explain me the dynamic algorithm, that finds number of subsets with sum equal to k. I searched in Google, but cant find any simple explanation! Sorry for my English! Here is the code:

int numbers[MAX];

int GetmNumberOfSubsets()
    {
        int dp[MAX];
        dp[0] = 1;
        int currentSum = 0;
        for (int i = 0; i < numbers.length; i++)
        {
            currentSum += numbers[i];
            for (int j = min(sum, currentSum); j >= numbers[i]; j--)
                dp[j] += dp[j - numbers[i]];
        }

        return dp[sum];
    }
c++algorithmdynamic-programming


Solution 1:[1]

You can use the following example to find the number of subsets with sum equal to k:

#include <iostream>

using std::cout;
using std::cin;

int count = 0,K;
void noofsubsets(int arr[], int sum, int N){
    if(N==0){
        if(sum==K)
            count++;
        return;
    }
    noofsubsets(arr, sum, N-1);
    noofsubsets(arr, sum+arr[N-1], N-1);
}

Solution 2:[2]

here is a solution using recursion ... considering two cases i) Including first element of an array. ii) without first array element.

`

def subSetsSumK(arr, v, k) :

    if (k == 0) :
        for value in v :
            print(value, end=" ")
        print()
        return
    
    if (len(arr)== 0):
        return
    si=0
    v1 = [] + v

    v1.append(arr[si])

    subSetsSumK(arr[1:], v1, k - arr[si])
    subSetsSumK(arr[1:], v, k)
   
def subSetsSumK(arr, k):

    v = []
    subSetsSumK(arr,v, k)


# Driver code

arr = [ 2,1,3,2 ]
k_sum = 4
subSetsSumK(arr,k)

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 Grant Miller
Solution 2 S Nagendra

Related Questions