寻找和为定值的多个数

<span style="font-family: Arial, Helvetica, sans-serif; background-color: rgb(255, 255, 255);">题目：</span>

输入两个整数n和sum，要求从数列1,2,3。。。n中随意取值，使得他们的和等于sum，列出所有的组合的可能情况

解法一：

        次类问题可以将n问题转化为n-1问题,递归即可：

（1）sum不包含n的情况，即sum 和 n-1

（2）sum包含n的情况，即sum-n，和n-1

代码如下：

void sumOfNums(int sum, int n, list<int> list) {
if (n <= 0 || sum <= 0) {
return;
}
if (sum==n) {
list.reverse();
for (std::list<int>::iterator iter = list.begin(); iter != list.end(); iter++) {
cout<< *iter << " + ";
}
cout << n << endl;
return;
}
list.push_front(n);
sumOfNums(sum - n , n - 1, list);//包含n
list.pop_front();
sumOfNums(sum , n - 1, list);//不包含n
}

解法二：回溯剪枝法

可以将此问题看成0-1背包问题，然后根据背包问题0-1路径回溯找出最后的解：

下面是一个背包问题的算法代码，已经测试通过：

#include "stdafx.h"
#include <iostream>

using namespace std;
int m, n = 5, x[10] = { 0 }, best[10] = { 0 };
int w[6] = { 0,2,2,6,5,5 }, v[6] = { 0,6,3,5,4,6 };
int c = 10;
int cw = 0, cv = 0, bestv = 0;
typedef bool BOOL; 
BOOL FALSE = false;
BOOL TRUE = true;
BOOL TestNode(int i, int j) {  // 第 i个物品的 候选值为0和1


   //更新相关参数值
cw += w[i] * j;
cv += v[i] * j;

//与之前的物品相比  有无冲突
if (cw>c)
return FALSE;

//无冲突，添加至解路径
x[i] = j;

// 到此为止  0--i行 均无冲突
// 如果是最后一行  成功找到一个解
if (i == n) {

for (i = 1; i <= n; i++)
printf("%d", x[i]);
if (cv > bestv) {
bestv = cv;
for (i = 1; i <= n; i++)
best[i]=x[i];
printf(" +best");
}

printf("\n");
return TRUE;

}

//如果不是最后一行 则判断i+1行

BOOL bSuit = FALSE;
for (int k = 0; k <= 1; k++)
{
//第i+1行存在合适位置 
if (TestNode(i + 1, k))
bSuit = TRUE;

//还原相关参数
cw -= w[i + 1] * k;
cv -= v[i + 1] * k;
}

return bSuit;

}



void  Bag()
{

for (int i = 0; i <= 1; i++)
{
cout<<TestNode(1, i)<<" ";
}

cout << endl;
cout << "---------------------------"<<endl;
cout << "最佳背包金额：" << bestv << endl;
for (int i = 0; i < n;i++) {
cout << best[i] << endl;
}


}

void main() {
Bag();
}