1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
swat32
3 years ago
12

Create a simple main() that solves the subset sum problem for any vector of ints. Here is an example of the set-up and output. Y

ou would fill in the actual code that makes it happen. int main() { int TARGET
Computers and Technology
1 answer:
OverLord2011 [107]3 years ago
6 0

Answer:

Let isSubSetSum(int set[], int n, int sum) be the function to find whether there is a subset of set[] with sum equal to sum. n is the number of elements in set[].

The isSubsetSum problem can be divided into two subproblems

…a) Include the last element, recur for n = n-1, sum = sum – set[n-1]

…b) Exclude the last element, recur for n = n-1.

If any of the above the above subproblems return true, then return true.

Explanation:

Using C++

// A recursive solution for subset sum problem

#include <stdio.h>

// Returns true if there is a subset of set[] with sun equal to given sum

bool isSubsetSum(int set[], int n, int sum)

{

// Base Cases

if (sum == 0)

return true;

if (n == 0 && sum != 0)

return false;

// If last element is greater than sum, then ignore it

if (set[n-1] > sum)

return isSubsetSum(set, n-1, sum);

/* else, check if sum can be obtained by any of the following

(a) including the last element

(b) excluding the last element */

return isSubsetSum(set, n-1, sum) ||

isSubsetSum(set, n-1, sum-set[n-1]);

}

// Driver program to test above function

int main()

{

int set[] = {3, 34, 4, 12, 5, 2};

int sum = 9;

int n = sizeof(set)/sizeof(set[0]);

if (isSubsetSum(set, n, sum) == true)

printf("Found a subset with given sum");

else

printf("No subset with given sum");

return 0;

}

Output:

Found a subset with given sum

You might be interested in
Choose the correct definition for Conditional Statement A. Affects the sequential flow of control by executing different stateme
Sliva [168]

Answer:

A: Affects the sequential flow of control by executing different statements based on the value of a Boolean expression

Explanation

because the real definition is Definition. A conditional statement is a statement that can be written in the form “If P then Q,” where P and Q are sentences. For this conditional statement, P is called the hypothesis and Q is called the conclusion. Intuitively, “If P then Q” means that Q must be true whenever P is true. And A, explain that.

5 0
3 years ago
Read 2 more answers
(ATRCKALLB) __________is an input device that contains a movable ball on the top.​
nikitadnepr [17]

Answer:

trackball

Explanation:

A trackball can be seen on a mouse.

3 0
2 years ago
What is your favorite film and what makes it good?
Gala2k [10]

Answer:

My Favorite film is The Old Guard

Explanation:

I like The Old Guard because it has action an etc.

4 0
2 years ago
Read 2 more answers
Where is the Outlook Search Folder located?
melamori03 [73]
When you go to the mail go to file and click new it should be in there as search folder
6 0
3 years ago
You must lower your high beams when within how many feet of an approaching vehicle?
drek231 [11]

2000 feet of any vehicle

7 0
3 years ago
Other questions:
  • PLS HELP ASAP! WILL GIVE BRAINLIEST!
    14·1 answer
  • Select the most likely outcome of making only on-time minimum payments to a credit
    11·1 answer
  • ______________ is only one of the marketing mix tools that acompany uses to achieve its marketing objectives.
    7·1 answer
  • #We've started a recursive function below called #measure_string that should take in one string parameter, #myStr, and returns i
    5·1 answer
  • Method x1() has code that calls method x2(). Method x2() has the following header.
    7·1 answer
  • What is the root of the tree?
    6·1 answer
  • Next, Leah wants to add a content slide that allows her to insert a table.
    8·2 answers
  • Consider the code below. When you run this program, what is the output if the temperature is 77.3 degrees Fahrenheit?
    6·1 answer
  • Anyone know how to delete it in my laptop
    10·1 answer
  • Is it better to try to prevent damage from natural disasters or to deal with disasters after they occur?
    10·2 answers
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!