C Program for Subset Sum Problem using Memoization
As seen in the previous recursion method, each state of the solution can be uniquely identified using two variables â the index and the remaining sum. So create a 2D array to store the value of each state to avoid recalculation of the same state.
Below is the implementation of the above approach:
C
#include <stdio.h>#include <string.h>// Taking the matrix as globallyint tab[2000][2000];// Check if a possible subset with // the given sum is possible or notint subsetSum(int a[], int n, int sum) { // If the sum is zero, it means // we got our expected sum if (sum == 0) return 1; if (n <= 0) return 0; // If the value is not -1, it means it // already called the function // with the same value. // It will save us from repetition. if (tab[n - 1][sum] != -1) return tab[n - 1][sum]; // If the value of a[n-1] is // greater than the sum, // we call for the next value if (a[n - 1] > sum) return tab[n - 1][sum] = subsetSum(a, n - 1, sum); else { // Here we do two calls because we // don't know which value fulfills our criteria. // That's why we're doing two calls return tab[n - 1][sum] = subsetSum(a, n - 1, sum) || subsetSum(a, n - 1, sum - a[n - 1]); }}int main() { // Storing the value -1 to the matrix memset(tab, -1, sizeof(tab)); int n = 5; int a[] = {1, 5, 3, 7, 4}; int sum = 12; if (subsetSum(a, n, sum)) { printf("YES\n"); } else { printf("NO\n"); } return 0;} |
Output
YES
Time Complexity: O(sum*n)
Auxiliary space: O(n)
C Program for Subset Sum Problem | DP-25
Write a C program for a given set of non-negative integers and a value sum, the task is to check if there is a subset of the given set whose sum is equal to the given sum.
Examples:
Input: set[] = {3, 34, 4, 12, 5, 2}, sum = 9
Output: True
Explanation: There is a subset (4, 5) with sum 9.Input: set[] = {3, 34, 4, 12, 5, 2}, sum = 30
Output: False
Explanation: There is no subset that adds up to 30.