这道题和以前做过的求和是一个思路,凑数(求和)题目如下:

链接:https://blog.nowcoder.net/n/a6b71a5651874650a65945e9bae8e5bf
这个题是一维的,直接把一段数字进行遍历,然后把能构成的都输出出来就行。
在遍历解空间过程中,适当剪枝可以增大程序的时间效率。

#include<iostream>
#include<vector>
using namespace std;
int n,m;
vector<int> vec;
void dfs(int i,int sum){
    if(sum==m){//凑够数了,进行输出
        for(int j=0;j<vec.size();j++){
            if(j==vec.size()-1){
                cout<<vec[j]<<endl;
            }else{
                cout<<vec[j]<<" ";
            }
        }
    }else{//没凑过数,继续进行遍历
        for(int j=i;j<=n&&sum<m&&j<=m;j++){//sum<m&&j<=m对树进行剪枝
            vec.push_back(j);
            dfs(j+1,sum+j);
            vec.pop_back();//凑够了就弹出,没凑够说明加上这个数不可能凑够,所以也弹出
        }
    }
}
int main(){
    while(cin>>n>>m){
        dfs(1,0);
    }
    return 0;
}

而这道题,更像是二维的一个递归,因为有两条线要走,要分别同时凑够两条线,
可以这么想,把5的倍数加起来存到sum5,把3的倍数加起来存到sum3,剩下的数存到vector数组里。
然后取sum5-sum3的绝对值,这样只需看数组里的数能否凑出两部分,使其差值是abs(sum5-sum3)。
如果可以构成,就说明可以。
但是重点是怎么用递归表示两条线呢?

我们可以这样想,先把所有的数都加起来,然后再依次减去所有的数,
可以看代码进行分析:

#include<iostream>
#include<vector>
#include<math.h>
using namespace std;
vector<int> elsevec;
int n,m,sum3,sum5,dis0; 
bool f(int i,int dis){
    if(i==elsevec.size()){
        return abs(dis)==dis0;
    }return (f(i+1,dis+elsevec[i])||f(i+1,dis-elsevec[i])); //**重点**
}
int main(){
    while(cin>>n){
        sum3=sum5=0;
        elsevec.clear();
        int t=n;
        while(t--){
            cin>>m;
            if(m%5==0){
                sum5+=m;    
            }else if(m%3==0){
                sum3+=m;
            }else{
                elsevec.push_back(m);
            }
        }dis0=abs(sum5-sum3);    
        if(f(0,0)){
            cout<<"true"<<endl;
        }else cout<<"false"<<endl;
    }
    return 0;
} 

代码的重点在于我标记的那个递推式:
我们可以画出解空间:

1 5 -5 1为例
图片说明