输入两个整数 n 和 m，从数列1，2，3.......n 中 随意取几个数,
使其和等于 m ,要求将其中所有的可能组合列出来。
我想，稍后给出的程序已经足够清楚了，就是要注意到放n，和不放n个区别，即可，代码如下：
// 21题递归方法
//copyright@ July && yansha
//July、yansha，updated。
#include<list>
#include<iostream>
using namespace std;
list<int>list1;
void find_factor(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); //典型的01背包问题
find_factor(sum-n, n-1); //放n，n-1个数填满sum-n
list1.pop_front();
find_factor(sum, n-1); //不放n，n-1个数填满sum
}
int main()
{
int sum, n;
cout << "请输入你要等于多少的数值sum:" << endl;
cin >> sum;
cout << "请输入你要从1.....n数列中取值的n：" << endl;
cin >> n;
cout << "所有可能的序列，如下：" << endl;
find_factor(sum,n);
return 0;
}@zhouzhenren：
这个问题属于子集和问题（也是背包问题）。本程序采用 回溯法+剪枝
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值。
代码编写如下：
//copyright@ 2011 zhouzhenren
//输入两个整数 n 和 m，从数列1，2，3.......n 中 随意取几个数,
//使其和等于 m ,要求将其中所有的可能组合列出来。
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
/**
* 输入t， r， 尝试Wk
*/
void sumofsub(int t, int k ,int r, int& M, bool& flag, bool* X)
{
X[k] = true; // 选第k个数
if (t + k == M) // 若找到一个和为M，则设置解向量的标志位，输出解
{
flag = true;
for (int i = 1; i <= k; ++i)
{
if (X[i] == 1)
{
printf("%d ", i);
}
}
printf("/n");
}
else
{ // 若第k+1个数满足条件，则递归左子树
if (t + k + (k+1) <= M)
{
sumofsub(t + k, k + 1, r - k, M, flag, X);
}
// 若不选第k个数，选第k+1个数满足条件，则递归右子树
if ((t + r - k >= M) && (t + (k+1) <= M))
{
X[k] = false;
sumofsub(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) // 预先排除无解情况
{
printf("not found/n");
return;
}
bool f = false;
sumofsub(0, 1, sum, M, f, X);
if (!f)
{
printf("not found/n");
}
free(X);
}
int main()
{
int N, M;
printf("请输入整数N和M/n");
scanf("%d%d", &N, &M);
search(N, M);
return 0;
}1、有N个数，组成的字符串，如012345，求出字串和取MOD3==0的字串，如012 12 123 45。
2、从一列数中筛除尽可能少的数使得从左往右看，这些数是从小到大再从大到小的（网易）。
3、有两个序列a,b，大小都为n,序列元素的值是任意整数，无序；
要求：通过交换a,b中的元素，使[序列a元素的和]与[序列b元素的和]之间的差最小。
例如:
var a=[100,99,98,1,2, 3];
var b=[1, 2, 3, 4,5,40];（微软100题第32题）。
@well：[fairywell]:
给出扩展问题 2 的一个解法：
1、从一列数中筛除尽可能少的数使得从左往右看，这些数是从小到大再从大到小的（网易）。
双端 LIS 问题，用 DP 的思想可解，目标规划函数 max{ b[i] + c[i] - 1 }, 其中 b[i] 为从左到右， 0 ~ i 个数之间满足递增的数字个数； c[i] 为从右到左， n-1 ~ i 个数之间满足递增的数字个数。最后结果为 n - max + 1。其中 DP 的时候，可以维护一个 inc[] 数组表示递增数字序列，inc[i] 为从小到大第 i 大的数字，然后在计算 b[i] c[i] 的时候使用二分查找在 inc[] 中找出区间 inc[0] ~ inc[i-1] 中小于 a[i] 的元素个数（low）。 源代码如下：
/**
* The problem:
* 从一列数中筛除尽可能少的数使得从左往右看，这些数是从小到大再从大到小的（网易）。
* use binary search, perhaps you should compile it with -std=c99
* fairywell 2011
*/
#include <stdio.h>
#define MAX_NUM (1U<<31)
int
main()
{
int i, n, low, high, mid, max;
printf("Input how many numbers there are: ");
scanf("%d/n", &n);
/* a[] holds the numbers, b[i] holds the number of increasing numbers
* from a[0] to a[i], c[i] holds the number of increasing numbers
* from a[n-1] to a[i]
* inc[] holds the increasing numbers
* VLA needs c99 features, compile with -stc=c99
*/
double a[n], b[n], c[n], inc[n];
printf("Please input the numbers:/n");
for (i = 0; i < n; ++i) scanf("%lf", &a[i]);
// update array b from left to right
for (i = 0; i < n; ++i) inc[i] = (unsigned) MAX_NUM;
//b[0] = 0;
for (i = 0; i < n; ++i) {
low = 0; high = i;
while (low < high) {
mid = low + (high-low)*0.5;
if (inc[mid] < a[i]) low = mid + 1;
else high = mid;
}
b[i] = low + 1;
inc[low] = a[i];
}
// update array c from right to left
for (i = 0; i < n; ++i) inc[i] = (unsigned) MAX_NUM;
//c[0] = 0;
for (i = n-1; i >= 0; --i) {
low = 0; high = i;
while (low < high) {
mid = low + (high-low)*0.5;
if (inc[mid] < a[i]) low = mid + 1;
else high = mid;
}
c[i] = low + 1;
inc[low] = a[i];
}
max = 0;
for (i = 0; i < n; ++i )
if (b[i]+c[i] > max) max = b[i] + c[i];
printf("%d number(s) should be erased at least./n", n+1-max);
return 0;
}@yansha：fairywell的程序很赞，时间复杂度O(N log N)，这也是我能想到的时间复杂度最优值了。不知能不能达到O(N)。
扩展题第3题
当前数组a和数组b的和之差为
A = sum(a) - sum(b)
a的第i个元素和b的第j个元素交换后，a和b的和之差为
A' = sum(a) - a[i] + b[j] - （sum(b) - b[j] + a[i])
= sum(a) - sum(b) - 2 (a[i] - b[j])
= A - 2 (a[i] - b[j])
设x = a[i] - b[j]，得
|A| - |A'| = |A| - |A-2x|
假设A > 0,
当x 在 (0,A)之间时，做这样的交换才能使得交换后的a和b的和之差变小，x越接近A/2效果越好,
如果找不到在(0,A)之间的x，则当前的a和b就是答案。
所以算法大概如下：
在a和b中寻找使得x在(0,A)之间并且最接近A/2的i和j，交换相应的i和j元素，重新计算A后，重复前面的步骤直至找不到(0,A)之间的x为止。
接上，@yuan：
a[i]-b[j]要接近A/2，则可以这样想，
我们可以对于a数组的任意一个a[k],在数组b中找出与a[k]-C最接近的数（C就是常数，也就是0.5*A）
这个数要么就是a[k]-C，要么就是比他稍大，要么比他稍小，所以可以要二分查找。
查找最后一个小于等于a[k]-C的数和第一个大于等于a[k]-C的数，
然后看哪一个与a[k]-C更加接近，所以T(N) = N log N。
除此之外，受本文读者xiafei1987128启示，有朋友在stacoverflow上也问过一个类似的题，:-)，见此：http://stackoverflow.com/questions/9047908/swap-the-elements-of-two-sequences-such-that-the-difference-of-the-element-sums。感兴趣的可以看看。
1、《挑战程序设计竞赛》的开票有个类似的抽签问题，挺有意思，题目如下：
将写有数字的n个纸片放入一个纸箱子中，然后你和你的朋友从纸箱子中抽取4张纸片，每次记下纸片上的数字后放回子箱子中，如果这4个数字的和是m，代表你赢，否则就是你的朋友赢。
请编写一个程序，当纸片上所写的数字是k1，k2，k3，k4，..，kn时，是否存在抽取4次和为m的方案，如果存在，输出YES；否则，输出NO。
限制条件：
- 1 <= n <= 50
- 1 <= m <= 10^8
- 1 <= ki <= 10^8
分析：最容易想到的方案是用4个for循环直接穷举所有方案，时间复杂度为O（N^4）,主体代码如下：
//通过4重for循环枚举所有方案
for (int a = 0; a < n, a++)
{
for (int b = 0; b < n; b++)
{
for (int c = 0; c < n; c++)
{
for (int d = 0; d < n; d++)
{
if (k[a] + k[b] + k[c] + k[d] == m)
{
f = true;
}
}
}
}
}但如果当n远大于50时，则程序会显得非常吃力，如此，我们需要找到更好的办法。
提供两个思路：
①最内侧关于d的循环所做的事情：检查是否有d满足ka+ kb +kc + kd = m，移动下式子，等价于：检查是否有d使得kd = m - ka - kb - kc，也就是说，只要检查k中所有元素，判断是否有等于m-ka-kb-ka 的元素即可。设m-ka-kb-ka = x，接下来，就是要看x是否存在于数组k中，此时，可以先把数组k排序，然后利用二分查找在数组k中找x；
②进一步，内侧的两个循环所做的事情：检查是否有c和d满足kc + kd = m - ka -kb。同样，可以预先枚举出kc+kd所得的n^2数字并排好序，便可以利用二分搜索继续求解。
2、给定整数a1、a2、a3、...、an，判断是否可以从中选出若干个数，使得它们的和等于k（k任意给定，且满足-10^8 <= k <= 10^8）。
分析：此题相对于本节“寻找满足条件的多个数”如出一辙，不同的是此题只要求判断，不要求把所有可能的组合给输出来。因为此题需要考虑到加上a[i]和不加上a[i]的情况，故可以采用深度优先搜索的办法，递归解决。