Find a combination of elements from different arrays

Question

I recently started learning C++ and ran into problems with this task: I am given 4 arrays of different lengths with different values.

   vector<int> A = {1,2,3,4};
    vector<int> B = {1,3,44};
    vector<int> C = {1,23};
    vector<int> D = {0,2,5,4};

I need to implement a function that goes through all possible variations of the elements of these vectors and checks if there are such values a from array A, b from array B, c from array C and d from array D that their sum would be 0(a+b+c+d=0) I wrote such a program, but it outputs 1, although the desired combination does not exist.

using namespace std;

    vector<int> test;
    int sum (vector<int> v){
        int sum_of_elements = 0;
        for (int i = 0; i < v.size(); i++){
            sum_of_elements += v[i];
        }
        return sum_of_elements;
    }
    
    bool abcd0(vector<int> A,vector<int> B,vector<int> C,vector<int> D){
        for ( int ai = 0; ai <= A.size(); ai++){
            test[0] = A[ai];
            for ( int bi = 0; bi <= B.size(); bi++){
                test[1] = B[bi];
                for ( int ci = 0; ci <= C.size(); ci++){
                    test[2] = C[ci];
                    for ( int di = 0; di <= D.size(); di++){
                        test[3] = D[di];
                        if (sum (test) == 0){
                            return true;
                        }
                    } 
                }
            }
        }
    }

I would be happy if you could explain what the problem is

Answer 1

Vectors don't increase their size by themself. You either need to construct with right size, resize it, or push_back elements (you can also insert, but vectors arent very efficient at that). In your code you never add any element to test and accessing any element, eg test[0] = A[ai]; causes undefined behavior.

Further, valid indices are [0, size()) (ie size() excluded, it is not a valid index). Hence your loops are accessing the input vectors out-of-bounds, causing undefined behavior again. The loops conditions should be for ( int ai = 0; ai < A.size(); ai++){.

Not returning something from a non-void function is again undefined behavior. When your abcd0 does not find a combination that adds up to 0 it does not return anything.

After fixing those issues your code does produce the expected output: https://godbolt.org/z/KvW1nePMh.

However, I suggest you to...

• not use global variables. It makes the code difficult to reason about. For example we need to see all your code to know if you actually do resize test. If test was local to abcd0 we would only need to consider that function to know what happens to test.
• read about Why is “using namespace std;” considered bad practice?
• not pass parameters by value when you can pass them by const reference to avoid unnecessary copies.
• using range based for loops helps to avoid making mistakes with the bounds.

Trying to change not more than necessary, your code could look like this:

#include <vector>
#include <iostream>

int sum (const std::vector<int>& v){
    int sum_of_elements = 0;
    for (int i = 0; i < v.size(); i++){
        sum_of_elements += v[i];
    }
    return sum_of_elements;
}
    
bool abcd0(const std::vector<int>& A,
            const std::vector<int>& B,
            const std::vector<int>& C,
            const std::vector<int>& D){

    for (const auto& a : A){
        for (const auto& b : B){
            for (const auto& c : C){
                for (const auto& d : D){
                    if (sum ({a,b,c,d}) == 0){
                        return true;
                    }
                } 
            }
        }
    }
    return false;
}

int main() {
    std::vector<int> A = {1,2,3,4};
    std::vector<int> B = {1,3,44};
    std::vector<int> C = {1,23};
    std::vector<int> D = {0,2,5,4};
    std::cout << abcd0(A,B,C,D);
}

Note that I removed the vector test completely. You don't need to construct it explicitly, but you can pass a temporary to sum. sum could use std::accumulate, or you could simply add the four numbers directly in abcd0. I suppose this is for exercise, so let's leave it at that.

Answer 2

Edit : The answer written by @463035818_is_not_a_number is the answer you should refer to.

---

As mentioned in the comments by @Alan Birtles, there's nothing in that code that adds elements to test. Also, as mentioned in comments by @PaulMcKenzie, the condition in loops should be modified. Currently, it is looping all the way up to the size of the vector which is invalid(since the index runs from 0 to the size of vector-1). For implementing the algorithm that you've in mind (as I inferred from your code), you can declare and initialise the vector all the way down in the 4th loop. Here's the modified code,

int sum (vector<int> v){
    int sum_of_elements = 0;
    for (int i = 0; i < v.size(); i++){
        sum_of_elements += v[i];
    }
    return sum_of_elements;
}

bool abcd0(vector<int> A,vector<int> B,vector<int> C,vector<int> D){

    for ( int ai = 0; ai <A.size(); ai++){
        for ( int bi = 0; bi <B.size(); bi++){
            for ( int ci = 0; ci <C.size(); ci++){
                for ( int di = 0; di <D.size(); di++){
                    vector<int> test = {A[ai], B[bi], C[ci], D[di]};
                    if (sum (test) == 0){
                        return true;
                    }
                } 
            }
        } 
    }
    return false;
}

The algorithm is inefficient though. You can try sorting the vectors first. Loop through the first two of them while using the 2 pointer technique to check if desired sum is available from the remaining two vectors

Answer 3

It looks to me, like you're calling the function every time you want to check an array. Within the function you're initiating int sum_of_elements = 0;.

So at the first run, you're starting with int sum_of_elements = 0;.
It finds the element and increases sum_of_elements up to 1.

Second run you're calling the function and it initiates again with int sum_of_elements = 0;.
This is repeated every time you're checking the next array for the element.

Let me know if I understood that correctly (didn't run it, just skimmed a bit).