CODEWITHSUNDEEP
c++algorithmdynamic-programming
James Rodrigues
James Rodrigues

Reputation: 107

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];
    }

Upvotes: 0

Views: 1809

Answers (3)

S Nagendra
S Nagendra

Reputation: 49

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)

Upvotes: 0

Vishal Singh
Vishal Singh

Reputation: 1501

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);
}

Upvotes: 0

amit
amit

Reputation: 178411

Your DP solution should be 2-dimensional, 1 dimension for the sum, and 1 dimension for the number of elements.

The recursive formula defining this solution is:

DP(x,i) = 0    x < 0
DP(0,i) = 1
DP(x,0) = 0    x > 0
DP(x,i) = DP(x-numbers[i],i-1) + DP(x,i-1)

And it should be something like:

    int dp[MAX+1][sum+1];
    int i, x;
    for (i = 0; i < MAX+1; i++) { 
         dp[i][0] = 1;
    }
    for (x = 1; x < sum+1; x++) { 
         dp[0][x] = 0
    }
    for (i = 1; i < MAX+1; i++) { 
       for (x = 1; x < sum+1; x++) { 
           dp[i][x] = dp[i-1][x];
           if (x >= numbers[i])
             dp[i][x] += dp[i][x-numbers[i]];
        }
     }
    return dp[MAX][sum];

(Hope I didn't have minor issues, didn't test it - but it should give you idea how to implement it once recursive formulas are clear)

Upvotes: 3

Related Questions