需要修改我的递归算法 [英] Need to modify my recursive algorithm

问题描述

这是一个子集和问题，它的工作正常，但我有一个问题。我需要在main中初始化z = 0。但是有一种方法，我可以做，而不初始化z = 0在主。

This is a subset sum problem and its working properly but I am having an issue. I need to initialize z=0 in the main. But is there a way that I could do it without initializing z=0 in the main.

所以根据主要应该返回true，因为根据子集和问题，向量中任何组合中的元素的总和应当等于target。

So according to the main it should return true because according to subset sum problem, the sum of the elements in the vector in any combination should be equal to target.

 bool r_x(vector<int> myvec, int y, int z=0){

        if( y == 0 )
            return true;

        if( z > myvec.size()-1)
            return false;

        return r_x(myvec, y, z+1) || r_x(myvec, y-myvec[z], z+1);
    }
int main(){
int z;
int y=7;

 vector<int> myvec;
    myvec.push_back(3);
    myvec.push_back(1);
    myvec.push_back(1);
    myvec.push_back(4);

r_x(vector<int> myvec, int z, int y);
}

OUTPUT：

false
false
false
false
false
false
false
true

输出应该为true，但是它应该是这样。

The output should be true but its like this.

推荐答案

这种标准方法是将递归函数包装在非递归函数中。

The standard approach to this is to wrap the recursive function in a non-recursive function

bool r_x_recursive(vector<int> myvec, int z, int y){

    if( y == 0 )
        return true;

    if( z > myvec.size()-1)
        return false;

    return r_x(myvec, z+1, y) || r_x(myvec, z+1, y-myvec[z]);
}

bool r_x(vector<int> myvec, int y) {
   return r_x_recursive(myvec, 0, y);
}

现在你可以调用 r_x ）。

这篇关于需要修改我的递归算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！