Knowee
Questions
Features
Study Tools

Given a set of non-negative integers, and a value S, determine if there is a subset of the given set with sum equal to S.

Question

Given a set of non-negative integers, and a value S, determine if there is a subset of the given set with sum equal to S.

🧐 Not the exact question you are looking for?Go ask a question

Solution

This problem can be solved using a method called dynamic programming. Here are the steps:

  1. Initialize a boolean 2D array dp[n+1][sum+1], where n is the size of the given set. The value of dp[i][j] will be true if there is a subset of the set with sum equal to j.

  2. Set dp[i][0] = true for all i, because there is always an empty subset with sum 0.

  3. Set dp[0][i] = false for all positive i, because there is no subset with positive sum when the set is empty.

  4. For each element in the set, iterate from 1 to n (i.e., for i=1 to n). For each possible sum from 0 to sum (i.e., for j=0 to sum), set dp[i][j] = dp[i-1][j] if dp[i-1][j] equals true or if the current element is less than or equal to the current sum and dp[i-1][j-element] equals true.

  5. Finally, return dp[n][sum]. If it is true, then there is a subset with sum equal to S. Otherwise, there is no such subset.

This problem has been solved

Similar Questions

Let S={1,2,3,5,7,10,11}. The number of non-empty subsets of S that have the sum of all elements a multiple of 3, is _____ .

Given an array, check if there exist 2 elements of the array such that their sum is equal to the sum of the remaining elements of the array.

The product of a set of positive integers is 1989. What is their least possible sum?

If A = {x : x ≤ 10 and x ∈ N}, B = {2} and C = {7} and S is a subset of A such that n(S ∩ B) = 1 and n(S ∩ C) = 0, how many such subsets are possible?

A partial sum of an arithmetic sequence is given. Find the sum. 22(7 − 8n)n = 0 S =

1/1

Upgrade your grade with Knowee

Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.