Is there a workaround for returning Null in c++ when the return type is a vector container?

user_12112359 0
Viewed 178

The thing is that I am implementing a recursion, in which I have to use NULL value to specify that the recursion branch being traversed is invalid.

But in C++ we can't return NULL when the return type is a container( vector container in my case).

So is there any workaround for the problem or do I have to use some other logic?

Code:

#include<iostream>
#include<vector>


std::vector<int> howSum(int target,std::vector<int> in){
    if(target < 0 ) return {-1}; 
    if(target == 0) return {};

    for(int num : in){
        int remainder = target - num ;
        std::vector<int> remResult = howSum(remainder,in);
        if(remResult[0] != -1 || remResult.empty()){
            remResult.push_back(num);
            return remResult;
        }
    }

    return {-1};
}

int main(){

    std::vector<int> v = {2,4,3};
    int targetSum = 8;

    std::vector<int> r = howSum(targetSum,v);

    for(int o : r)
        std::cout<<o<<" ";

    return 0;
}

Edit:

I'm very thankful for all the suggestions and solution but thing I wanted was a primitive solution that didn't use more recent c++ compilations(i.e c++17 and c++20). Also If possible please check out my primitive solution which I implemented and suggest something if this can be improved.

An alternate solution I found out myself (primitive solution)

I am writing this for people visiting this question for reference.

Solution:

#include<iostream>
#include<vector>
#include<string>

std::string howSum(int target,std::vector<int> v){

    if(target == 0)    return "";
    if(target < 0)     return "null";
    
    for(int num : v){
        int rem = target - num;
        std::string remRes = howSum(rem,v);
        if(remRes != "null"){
            remRes += std::to_string(num);
            remRes += " ";
            return remRes;
        }
        
    }
    return "null";
}

int main()
{
    std::vector<int> v = {2,3,4};
    int targetSum = 8;
    
    std::cout<<howSum(targetSum,v);
    return 0;
}

My Dynamic Problem Solution

#include<iostream>
#include<vector>
#include<string>
#include<unordered_map>

std::unordered_map<int,std::string> mem;

std::string howSum(int target, std::vector<int> v){
    if(mem.find(target) != mem.end())
        return mem[target];
    if(target == 0)    return "";
    if(target < 0)     return "null";
    
    for(int num : v){
        int rem = target - num;
        std::string remRes = howSum(rem,v);
        if(remRes != "null"){
            remRes += std::to_string(num);
            remRes += " ";
            mem[target] = remRes;
            return mem[target];
        }
        
    }
    mem[target] = "null";
    return mem[target];
}

int main()
{
    std::vector<int> v = {7,14};
    int targetSum = 300;
    
    std::cout<<howSum(targetSum,v);
    return 0;
}
c++14 recursion c++
2 Answers

You have the following options:

Return result + bool

Return std::pair<std::vector<int>, bool>, or even better a struct like this

struct Result {
    std::vector<int> result;
    bool is_valid;
};

Result howSum(int target, const std::vector<int>& in);

where bool would indicate whether or not the result vector is actually usable.

Output parameter

Return a bool indicating whether the operation was successful and use an output parameter (note that a non-const reference is used for the output parameter so that it can be modifier from within the function and later used outside of it):

bool howSum(int target, const std::vector<int>& in, std::vector<int>& result);

optional

Either use std::optional with C++17 or a similar boost::optional from boost library:

std::optional<std::vector<int>> howSum(int target, const std::vector<int>& in);

Casting std::optional to bool or using has_value method checks whether you have an actual result returned.

Note that in each of the cases it's better to pass the input vector by const & to avoid unnecessary copies.

user_125011370

with optional (c++17), you could do something like this

#include<iostream>
#include<vector>
#include<optional>


std::optional<std::vector<int>> howSum(int target,std::vector<int> in){
    if(target <= 0 ) return {}; // returns "empty" optional

    auto num = in.back();
    in.pop_back();
    int remainder = target - num ;
    auto maybe_r = howSum(remainder, in);
    if (!maybe_r.has_value())
        return howSum(target, in);
    else {
        auto r = maybe_r.value();
        r.push_back(num);
        return r;
    }
}

int main(){

    std::vector<int> v = {2,4,3,1};
    int targetSum = 8;

    auto maybe_r = howSum(targetSum,v);

    if (!maybe_r.has_value()) {
        std::cout << "no result\n";
    } else {

        auto r = maybe_r.value();
        for(int o : r)
            std::cout<<o<<" ";

    }
    return 0;
}
user_54947210
Related