The Language is C++. DO NOT CHANGE THE ORIGINAL CODE, ONLY ADD CODE WHERE "your code here" IS WRITTEN. Use Comments to explain techniques used/ why they were used.

Problem 3: Divide a vector by sum (40 + 5 points) In this problem, given a non-empty vector nums that only has positive integers, you are going to find if this vector can be divided into two subsets, such that the sum of elements in both subsets is equal. Any element can only exist in one of the two subsets. For example: Input: nums = {1,5,11,5}. Output: true. The two subsets are {1,5,5} and {11} Input: nums = {1,2,3,5}. Output: false. We cannot find two equal sum subsets.

The starter code is here: https://onlinegdb.com/ADMCN6-GZ Hint 1: This problem basically reduces to determining if there exists a subset of the vector such that the sum of elements in it is half of the total sum of nums. Hence, you only need to make a small modification of our subset codes in the lecture. Hint 2: Be careful of the integer division. Use double to ensure it is a decimal number if you like. Bonus task (5 points): However, if we directly use the modification of our subset codes, there would be an issue, which will cause your codes to be very slow. Can you point it out? Hint: Draw the tree of recursive calls for the following input and then you will see the issue:) nums = {1,1,1,1,1,1,1,1,1,1,1,1} (i.e., 12 ones).

Starter Code

#include #include using namespace std;

/* A simple modification of our subsets code will work. If necessary, you can also write your own helper function. ----------------------------------------------------------------------------- */ bool mySumHelper(vector &nums, int index, int currentSum, double target) { // your code here... }

bool mySum(vector &nums) { // your code here... } /* ----------------------------------------------------------------------------- */

int main() { vector num1 = {1, 5, 11, 5}; cout << mySum(num1) << endl;

vector num2 = {1, 1, 1, 1}; cout << mySum(num2) << endl;

vector num3 = {1, 2, 3, 5}; cout << mySum(num3) << endl; }