This is an Amazon Interview Qeustion for Dev Leads from careercup. The following is the original problem description of that thread.
"
Given a set of number eg {5,3,1,8, -8,-4}
Print all subset which will sum up to ZERO
for eg {3,1,-4} {5,3,-8}, {8,-8}
Note : size of subset can be max 100 and element can be very big like 13 or 14 digit number
"
2. Analysis
Initially I thought that we could simply use brutal force to compute the POWER set of the given set. Please refer to Dynamic programming - Generate power set given a set. Then sum of the elements of each sub set and compare if the sum is equal to zero. The sub sets with the sum equal to zero are what we are hunting for. But this turns out impossible because the space complexity of the POWER set, which requires exponential space complexity, O(2^N), where N is the size of the given set. According to the problem description N could reach 100. It is impossible to cache the POWER SET.
In this blog I am going to present a brutal force DP solution of with O(2^N) computation complexity and O(N) space complexity, which N is the size of the given set. Now let's take a look at the sub problem.
Sub-problem:
Assume the given size of SET is N. Let's consider a sub-set of previous 0, ..., i-1 elements as Subset(i-1). Now we are encountering the i-th element. What we need to do,
- Check if Subset(i-1) is what we are hunting for. If the sum of elements is equal to zero, print.
- Do not take i-th element into this subset and considering the rest of elements in the given set
- Take the i-the element int this subset and considering the rest of the elements in the given set.
Assumption:
- Repetitive elements are considered different. You can view the print out are the index of elements. Therefor given a set {0, 0, 0}, it is considered that there are 7 different combinations
{a0}, {a1}, {a2}, {a0, a1}, {a0, a2},{a1, a2} and {a0, a1, a2}, where a0 = a1 = a2 = 0.
3. C++ Implementation
// ********************************************************************************
// IMPLEMENTATION
// ********************************************************************************
#include <iostream>
#include <iterator>
#include <vector>
using SET = std::vector<int>;
const std::vector<size_t>& indicesOfSubset,
const size_t sizeOfSubset)
{
if (sizeOfSubset == 0) {
return;
}
std::cout << "{ " << input[indicesOfSubset[0]];
for (size_t index = 1; index < sizeOfSubset; ++index) {
std::cout << "; " << input[indicesOfSubset[index]];
}
std::cout << " }" << std::endl;
}
size_t PrintSubSetOfSummOfAllElementsEqualZero_DP(const SET& input,
const size_t indexOfNext,
std::vector<size_t>& indicesOfSubset,
const int sumOfSubset,
const size_t sizeOfSubset,
bool alreadyCounted)
{
size_t count = 0;
if (sumOfSubset == 0 && !alreadyCounted) {
PrintOutSubSet(input, indicesOfSubset, sizeOfSubset);
alreadyCounted = true;
++count;
}
if (indexOfNext < input.size()) {
count += PrintSubSetOfSummOfAllElementsEqualZero_DP(input,
indexOfNext + 1,
indicesOfSubset,
sumOfSubset,
sizeOfSubset,
alreadyCounted);
indicesOfSubset[sizeOfSubset] = indexOfNext;
count += PrintSubSetOfSummOfAllElementsEqualZero_DP(input,
indexOfNext + 1,
indicesOfSubset,
sumOfSubset + input[indexOfNext],
sizeOfSubset + 1,
false);
}
return count;
}
size_t PrintSubSetOfSummOfAllElementsEqualZero(const SET& input)
{
auto SIZE_OF_INPUT = input.size();
std::vector<size_t> indicesOfSubset(SIZE_OF_INPUT, 0);
size_t count = 0;
for (size_t index = 0; index < SIZE_OF_INPUT; ++index) {
indicesOfSubset[0] = index;
count += PrintSubSetOfSummOfAllElementsEqualZero_DP(input,
index + 1,
indicesOfSubset,
input[index],
1,
false);
}
return count;
}
// ********************************************************************************
// TEST
// ********************************************************************************
#include <cassert>
void TestPrintSubSetOfSummOfAllElementsEqualZero()
{
{
const SET testSet = { 5, 3, 1, 8, -8, -4 };
assert(PrintSubSetOfSummOfAllElementsEqualZero(testSet) == 4);
}
{
const SET testSet = { 0, 0, 0 , 0 };
assert(PrintSubSetOfSummOfAllElementsEqualZero(testSet) == 15);
}
{
const SET testSet = { -1, 1 };
assert(PrintSubSetOfSummOfAllElementsEqualZero(testSet) == 1);
}
{
const SET testSet = { -1, 1, -3, 3 };
assert(PrintSubSetOfSummOfAllElementsEqualZero(testSet) == 3);
}
{
const SET testSet = { -1, 1, -3, 3, -4, 4 };
assert(PrintSubSetOfSummOfAllElementsEqualZero(testSet) == 9);
}
{
const SET testSet = { -1, 1, -2, 2, -3, 3, -4, 4 };
assert(PrintSubSetOfSummOfAllElementsEqualZero(testSet) == 25);
}
{
const SET testSet = { -1, 1, -2, 2, -3, 3, -4, 4, -5, 5 };
assert(PrintSubSetOfSummOfAllElementsEqualZero(testSet) == 75);
}
}
// ********************************************************************************
No comments:
Post a Comment