Comparing returned vectors from recursion tree branches

user_4080322 0
Viewed 207

Suppose I have a given sum, say sum = 4. I am also given a vector = {2,4}. There are two ways to generate the given sum from the given vector (elements may be reused). One way is just {4} cause 4 = 4. Second way is {2,2} cause 2 + 2 = 4. I have to find the shortest possible combination, therefore in this particular case the answer is {4}.

Here is my approach - I go through the tree, and when on the leaf I get a 0, we hit the base case, return {} vector, and fill up the vector while traversing the tree. When I get to a node, I choose the smaller of the two (or more) vectors. This way when I reach the root node, I should get a vector of the shortest combination that can yield me the target sum.

As of yet, I do not care about time constraints as such, I know there's a lot of repetitive computing going on so I will have to memoize it once I can get the basic version correct.

I have been trying to figure why this code is not working. Any insight would be appreciated.

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

vector<int> findBestSum(int targetSum, const vector<int> &elements, vector<vector<int>> &temp) {
    if (targetSum == 0)
        return {};
    else if (targetSum < 0)
        return {-1};
    else {
        vector<int> small;
        for (auto &i : elements) {
            int remainder = targetSum - i;
            vector<int> returnedVector = findBestSum(remainder, elements, temp);
            if ((!returnedVector.empty() && find(returnedVector.begin(), returnedVector.end(), -1) == returnedVector.end()) || returnedVector.empty()) {
                returnedVector.push_back(i);
                temp.push_back(returnedVector);
            }
            int smallestLength = temp[0].size();
            for (auto &j : temp)
                if (smallestLength >= j.size())
                    small = j;
        }
        return small;
    }
}

int main() {
    int targetSum = 6;
    const vector<int> elements{2, 3, 5}; // answer should be [3,3] however I just get a 3...
    vector<vector<int>> temp;
    vector<int> bestSumVector = findBestSum(targetSum, elements, temp);
    for (auto i : bestSumVector)
        cout << i << " ";
}

Update (14th of July, 2021):

After a few busy months I have tried to lock horns with this problem and this time my code looks like this:

#include <iostream>
#include <vector>
#include <map>
#include <numeric>

using namespace std;

bool howSum(int &targetSum, vector<int> &elementVector, vector<int> &howSumVector, vector<vector<int>> &allSums) {
    static int originaltargetsum = targetSum;
    if (targetSum == 0)
        return true;
    else if (targetSum < 0)
        return false;
    else {
        for (auto i : elementVector) {
            int remainder = targetSum - i;
            bool flag = howSum(remainder, elementVector, howSumVector, allSums);
            if (flag) {
                howSumVector.push_back(i);
                if (targetSum == originaltargetsum ||
                    accumulate(howSumVector.begin(), howSumVector.end(), 0) == originaltargetsum) {
                    allSums.push_back(howSumVector);
                    howSumVector.clear();
                }
                return true;
            }
        }
        return false;
    }
}

int main() {
    int sum = 8; 
    vector<int> elements = {1, 4, 5}; 
    vector<vector<int>> allSums = {};
    vector<int> workingBench = {};
    howSum(sum, elements, workingBench, allSums);
    for (auto &i : allSums) {
        for (auto &j : i) {
            cout << j << " ";
        }
        cout << endl;
    }
}

For this I have sum as 8 and elements as {1, 4, 5}. Also I'm storing and displaying all possible solutions right now (once that is correctly done, finding shortest vector and memoization should be easy). Possible solutions in this case are:

[1, 1, 1, 1, 1, 1, 1, 1]
[4, 4]
[5, 1, 1, 1]
[4, 1, 1, 1, 1]

Currently my code only shows the first possible combination. I'm pretty sure I'm returning true and false incorrectly, please help me out here.

subset-sum dynamic-programming recursion c++
2 Answers

I took a stab at this. I do have a working solution, hopefully it is what you want:

#include <iostream>
#include <vector>
#include <algorithm>

void howSum(int targetSum, const std::vector<int> & elementVector, const std::vector<int> & howSumVector, std::vector<std::vector<int>> & allSums)
{
    static int originaltargetsum = targetSum;

    if (targetSum == 0)
    {
        allSums.push_back(howSumVector);
        return;
    }
    else if (targetSum < 0)
    {
        return;
    }
    else
    {
        for (const auto i : elementVector)
        {
            // an element less than or equal to 0 would cause an infinite loop
            if (i <= 0)
                continue;

            std::vector<int> newSumVector = howSumVector;
            newSumVector.push_back(i);

            std::vector<int> newElementVector;
            std::copy_if(std::begin(elementVector), std::end(elementVector), std::back_inserter(newElementVector), [i](int element){ return element >= i; });

            howSum(targetSum - i, newElementVector, newSumVector, allSums);
        }
    }
}

int main()
{
    int sum = 8;
    std::vector<int> elements = { 1, 4, 5 };
    std::vector<std::vector<int>> allSums = {};
    std::vector<int> workingBench = {};

    howSum(sum, elements, workingBench, allSums);

    for (const auto & i : allSums)
    {
        for (const auto & j : i)
        {
            std::cout << j << " ";
        }

        std::cout << std::endl;
    }

    return 0;
}

I think, in general, you were over-thinking or over-engineering the problem. Like others have mentioned, your current code is returning true too early, and nothing besides the first element/combination is tested. With recursion, it is important to take care in your return cases - really, you only want a base case or two, and otherwise you want to recur.

With the solution I have here, the main thing I have added is copying the current combination of elements for each element you need to test. That solves your main issue of not testing every combination of numbers. In addition to that, it seemed better to append to allSums when the targetSum was reached. With those changes, I was able to do away with the bool return value and simplify the code a bit. Running the code above gives these solutions:

1 1 1 1 1 1 1 1
1 1 1 1 4
1 1 1 4 1
1 1 1 5
1 1 4 1 1
1 1 5 1
1 4 1 1 1
1 5 1 1
4 1 1 1 1
4 4
5 1 1 1

This does have some duplicates (because of the order things are tested) but I felt like it is good enough since you only want the smallest solution, 4 4. To find this, you would just need to sort the allSums vector by inner vector size and then take the first entry.

user_13590340

I think you need to change the implementation to correctly process elements of the vector. In your implementation it doesn't go over all vector items, just the first one. This is one way to do it if you use vector elements as the first parameter in your function.

vector<int> findBestSum(int element, int targetSum, const vector<int>& elements, 
vector<vector<int>>& temp) {
if (targetSum == 0)
    return {};
else if (targetSum < 0)
    return { -1 };
else {
    int remainder = targetSum - element;
    vector<int> returnedVector = findBestSum(element, remainder, elements, temp);
    if ((!returnedVector.empty() && find(returnedVector.begin(), returnedVector.end(), -1) == returnedVector.end()) || returnedVector.empty()) {
        returnedVector.push_back(element);
        return returnedVector;
    }
    return returnedVector;
}

}

int main() {
  const int targetSum = 6;
  const vector<int> elements{ 2, 3, 5 }; // answer should be [3,3] however I just get a 3...
  vector<vector<int>> temp;
  for (auto i : elements) {
      vector<int> returnedVector = findBestSum(i, targetSum, elements, temp);
      if ((!returnedVector.empty() && find(returnedVector.begin(), returnedVector.end(), -1) == returnedVector.end()) || returnedVector.empty())
          temp.push_back(returnedVector);
  }

  if (temp.size() > 0) {
      vector<int> bestSum = {};
      size_t small = 0;
      size_t smallestLength = temp[0].size();
      for (auto& j : temp)
          if (smallestLength >= j.size()) {
              small = j.size();
              bestSum = j;
          }
      for (auto i : bestSum)
          cout << i << " ";
    }
    else
        cout << " sum not found" << endl;
}
user_27338370
Related