Coderust: Hacking the Coding Interview/

...

/

Find K-Sum Subsets

Find K-Sum Subsets

Given a set of positive integers, find all the subsets of the given array that sum up to a number K.

We'll cover the following...

Statement

Given a seta set contains distinct objects of n positive integers, find all the possible subsets of integers that sum up to a number K.

The following example elaborates this statement further:

Example

In the below example, we can see three possible subsets that sum to K = 10.

g array Set of integers 1 3 5 21 19 7 2 array2 Subsets that sum to K=10 {3,7} {3,5,2} {1,7,2}

Sample input

set_of_integers = {1, 3, 5, 21, 19, 7, 2}
K = 10

Expected output

{{3, 7}, {3, 5, 2}, {1, 7, 2}}

Try it yourself #

#include <iostream>
#include <string>
#include <vector>
#include <unordered_set>
using namespace std;
vector<unordered_set<int>> GetKSumSubsets(vector<int>& setOfIntegers, int targetSum) {
	//TODO: Write - Your - Code
	vector<unordered_set<int>> subsets;
	return subsets;
}

Solution 1

We know that for a set of n elements, there are 2n2^n subsets. For example, a set with 33 ...