寻找和为定值的多个数
题目描述：
输入两个整数 n 和 sum ，从数列 1，2，3 ....... n 中随意取几个数，使其和等于 sum，要求将其中所有的可能组合列出来。
分析和解法：
解法一：n 问题转化为 n-1 问题
注意到取 n，和不取 n 的区别即可，考虑是否取第 n 个数的策略，可以转化为一个和前 n-1 个数相关的问题。
- 如果取第 n 个数，那么问题就转化为 “ 取前 n-1 个数使得它们的和为 sum-n ”，对应的代码语句就是
sumOfkNumber(sum - n, n - 1)； - 如果不取第 n 个数，那么问题就转化为 “ 取前 n-1 个数使得他们的和为 sum ”，对应的代码语句为
sumOfkNumber(sum, n - 1);
源代码如下：
#include <iostream>
#include <list>
using namespace std;
list<int>list1;
void SumOfkNumber(int sum, int n)
{
//递归出口
if (n <= 0 || sum <= 0)
return;
//输出找到的结果
if (sum == n)
{
//反转 list
list1.reverse();
for (list<int>::iterator iter = list1.begin(); iter != list1.end(); iter++)
cout << *iter << "+" ;
cout << n << endl;
list1.reverse(); //此处还需反转回来
}
list1.push_front(n); //典型的 0/1 背包问题
SumOfkNumber(sum - n, n - 1); //“放”n，前n-1个数“填满”sum-n
list1.pop_front();
SumOfkNumber(sum, n - 1); //不“放”n，n-1个数“填满”sum
}
int main()
{
int a[100];
int n;
cin >> n;
int sum;
cin >> sum;
SumOfkNumber(sum, n);
return 0;
}
分析：递归调用，注意语句先后顺序。时间复杂度为 O（n ^ 2）。反转链表输出是为了体现思考过程，即函数执行过程。
解法二：回溯 + 剪枝
这个问题属于子集和问题（也是背包问题），故可采用回溯 + 剪枝的方法，定义 X 数组是解向量，t = ∑(1, ..., k-1)Wi * Xi， r = ∑(k, .., n)Wi，且
- 若 t + Wk + W(k+1) <= M,则 Xk = true，递归左儿子 (X1,X2,..,X(k-1),1)；否则剪枝；
- 若 t + r - Wk >= M && t + W(k+1) <= M,则置 Xk = 0，递归右儿子 (X1,X2,..,X(k-1),0)；否则剪枝；
本题中 W 数组就是 (1,2,..,n) ，所以直接用 k 代替 WK 值。
源代码如下：
#include <iostream>
#include <cstring>
#include <cstdlib>
using namespace std;
//输入 t 和 r ，尝试 Wk
void SumOfkNumber(int t, int k, int r, int& M, bool& flag, bool* X)
{
X[k] = true; //选第 k 个数
if (t + k == M)
{
flag = true;
for (int i = 1; i <= k; i++)
{
if (X[i] == 1)
cout << i << " " ;
}
cout << endl;
}
else
{
//若第 k+1 个数满足条件，则递归左子树
if (t + k + (k + 1) <= M)
SumOfkNumber(t + k, k + 1, r - k, M, flag, X);
//若不选第 k 个数，选第 k+1 个数满足条件，则递归右子树
if ((t + r - k >= M) && (t + (k + 1) <= M))
{
X[k] = false;
SumOfkNumber(t, k + 1, r - k, M, flag, X);
}
}
}
void Search(int& N, int& M)
{
//初始化解空间
bool* X = (bool*)malloc(sizeof(bool) * (N + 1));
memset(X, false, sizeof(bool) * (N + 1));
int sum = (N + 1) * N * 0.5f;
if (1 > M || sum < M) //预先排除无解情况
{
cout << "not found" << endl;
return;
}
bool f = false;
SumOfkNumber(0, 1, sum, M, f, X);
if (!f)
cout << "not found" << endl;
free(X);
}
int main()
{
int n;
cin >> n;
int sum;
cin >> sum;
Search(n, sum);
return 0;
}
分析：这个算法比较好理解，但是函数实现过程有点费解。
特别注意：
- 这种问题都是从后向前考虑，递归向下求解
参考资料：《编程之法》The Art of Programming By July
