检查是否可从数组上的算术运算中获得值

Question

很抱歉没有正确构图标题，但基本上是这样的：

给定一个大小为 n 的数组，元素为_0，a1，a2...一个_n-1 和一个值 K，通过在每个元素前插入 + 或 - （至少一个）来找出是否可以获得 K。如果可获取，请打印"是"，否则"否"。必须使用所有数字。

例如：

输入：
4 6
1 2 3 4

输出：
是的

解决方案 ： 1 - 2 + 3 + 4

输入：
4 7
1 2 3 4

输出：
不

我觉得完全有可能找到dp解决方案。

Answer 1

这是递归：

bool Recursion( int* myarray, int result, int size ){
    myarray[0] *= -1;
    if( size == 1 ){
        if( result == myarray[0] )
            return true;
    }
    else if( Recursion( (myarray+1), (result-myarray[0]), size-1 ) ) 
        return true;
    myarray[0] *= -1;
    if( size == 1 ){
        if( result == myarray[0] )
            return true;
    }
    else if( Recursion( (myarray+1), (result-myarray[0]), size-1 ) ) 
        return true;
    return false;
}

这是主要实现：

void printarray( int* myarray, int size ){
    for( int i = 0; i < size ; i++ ){
        std::cout << myarray[i];
        if( i != size-1 )
            std::cout << " + ";
    }
    std::cout << std::endl;
}
int main(){
    const int size = 4;
    const int result = 6;
    int myarray[size] = {1,2,3,4};
    bool test = Recursion( myarray, result, size );
    if( test ){
        std::cout << "YES... Solution: ";
        printarray( myarray, size );
    }
    else{
        std::cout << "NO... " << std::endl;
        printarray( myarray, size );
    }
    system("pause");
    return 0;
}

但是，我会把它留给你来阅读。