数组两个数和目标树数组中任选几个数相加，使其等于一个给定的值。请给出c++实现或者算法描述。

2020-10-02知识8

LeetCode按照怎样的顺序来刷题比较好？本题已加入知乎圆桌「高效刷LeetCode拿Offer！来围观计算机专业找工作方面值得关注的信息吧。更多讨…

数组中任选几个数相加，使其等于一个给定的值。请给出c++实现或者算法描述。这个问题又称为“子集和问题”（也就是给定一个整数集合和一个定值，从一个集合中选取一个子集，使得子集中所有数的和等于给定的值，具体的可以，google 子集和问题），这是一个NP完全问题，不存在多项式时间的解，所以没有好的算法。算法可以网上搜一下。下面是我替你搜的的一个（回溯法：遇到合适的就取，取到后面的时候满足不了，就后退，重新取下一个满足的）：输入：数组长度定值数组中的数例如：5 104 5 2 6 2输出：4 6includeusing namespace std；includeint len；int sum；int data[100000]；数据.char output[100000]；所求子集元素，与输入数据对应，'Y'为取.‘N’为不取void GetInput(){int i；cin>；>；len>；>；sum；for(i=0；i；i+){scanf(\"%d\"，&data[i])；output[i]='N'；}}int GetRes(){int p=0；指向当前值.int temp=0；当前子集合和.while(p>；=0){if('N'=output[p]){选中当前项.output[p]='Y'；temp+data[p]；if(temp=sum){return 1；}else if(temp>；sum){output[p]='N'；temp-=data[p]；}p+；}if(p>；=len){while('Y'=output[p-1]){p-；output[p]='N'；temp-=data[p]；if(p){return 0；}}while('N'=output[p-1]){p-；if(p){return 0；}}output。

数组两个数和目标树数组中任选几个数相加，使其等于一个给定的值。请给出c++实现或者算法描述。