PART 1: The 3 sum problem: Provided a 1D array of integers, find all combination
ID: 3547883 • Letter: P
Question
PART 1:
The 3 sum problem:
Provided a 1D array of integers, find all combinations of 3 values from this set such that: a+b+c=0
For example, if one were provided with the set [3 1 3 -4 -6], the resulting answers would be [3 1 -4], [3 1 -4], and [3 3 -6], as these are the three sets of three values which sum to zero from the provided set. Notice that the first and second solution appear to be the same, but correspond to two solutions for the two different 3s in the provided set.
Your code should return the answer in 2D array format, where each row is a solution set (3 columns per row). If no solution sets can be found for a given input, the code should output a value of zero.
For this assignment you should find or develop an algorithm for finding these solutions. Once you have found or developed this algorithm, create a flowchart for this algorithm.
Your code should be adequately commented, such that one would be able to understand your code by reading comments only. Your code should also include an initial code block giving a brief overview of how to use the function and your solution process, so that someone can query your program for this code block using the help command.
Please do NOT use the MATLAB built-in functions perms(), nchoosek(), or the like. This means you should loop through the array yourself to find the required sets.
PART 2:
Develop and implement a method to identify and remove and solutions which are numerically equivalent, so that the result from your code doesn't have any repeated solutions. This should be able to match solutions which contain the same values but in different orders. This means that if the sets [3 1 -4] and [3 -4 1] are in the solution your method should still identify them as equivalent and only return one of them.
-------
I'm very new to Matlab. Please help me with this problem. Please show all the works as 2 separate parts. Please create a flow chart for part 1 if you can.I will rate and give you all the points!!
Explanation / Answer
set<vector<int> > find_triplets(vector<int> arr) {
sort(arr.begin(), arr.end());
set<vector<int> > triplets;
vector<int> triplet(3);
int n = arr.size();
for (int i = 0;i < n; i++) {
int j = i + 1;
int k = n - 1;
while (j < k) {
int sum_two = arr[i] + arr[j];
if (sum_two + arr[k] < 0) {
j++;
} else if (sum_two + arr[k] > 0) {
k--;
} else {
triplet[0] = arr[i];
triplet[1] = arr[j];
triplet[2] = arr[k];
triplets.insert(triplet);
j++;
k--;
} }
}
return triplets;
}
Note that a set is chosen to store the triplets, because we are only interested in unique triplets. Since the set S is already sorted, and we don
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.