问题描述：

输入两个整数n 和m，从数列1，2，3.......n 中随意取几个数,使其和等于 m ,要求将其中所有的可能组合列出来。这是一个简单的背包问题

算法：

有一些分析认为此题有两种思路：递归和非递归。

但是我觉得“是否递归”只是形式上的区别，用来代表两种思路有点牵强。

我认为应该从算法的处理过程来区分：

第一种：检查所有的组合，去掉和不为m的组合。直观地可将算法分成两步①产生所有子集②挑选符合要求的子集

第二种：构造组合，在产生组合的过程中检测组合的合法性，若发现已不可能构造出合法组合，则停止操作。（如组合中已有元素的和已大于m，则不再继续）

打个不太准确的比喻：就像一棵树，第一种是先生成树，再对叶节点（生成的结果）进行挑选。第二种是在生成树的过程中，及时剪掉不合法的枝，只产生合法的叶节点。

算法实现：

第二种思路的递归实现：

#pragma once
#include
using namespace std;

void Out(int flag[], int size)
{
?for (int i = 0; i < size; i++)
? if (flag[i] == 1)
? ?cout << i + 1 << ' ';
?cout << endl;
}

bool Equal(int flag[], const int size, int sum)
{
?for (int i = 0; i < size; i++)
? if (flag[i] == 1)
? ?sum = sum - (i + 1);
?if (sum == 0)
? return true;
?return false;
}

void Find(int n, int m, int flag[], const int size, const int sum)
{
?if (n < 1)
?{
? if (Equal(flag, size, sum))
? ?Out(flag, size);
? return;
?}
?if (m >= n)
?{
? flag[n - 1] = 1;
? Find(n - 1, m - n, flag, size, sum);
? flag[n - 1] = 0;
? Find(n - 1, m, flag, size, sum);
?}
?if (m < n)
? Find(m, m, flag, size, sum);
}

void? main()
{
?int n, m;
?cin >> n >> m;
?int *flag = new int[n];
?cout << "所有可能的组合:" << endl;
?Find(n, m, flag, n, m);
?system("pause");
}

另外，若削减上述递归代码的限制，可以写出第一种思路的递归代码，实际上是递归产生子集的算法的一种变形。这从另一个角度说明，递归与否只是形式，真正的区别是算法的处理过程。代码如下：

#pragma once
#include
using namespace std;

void Out(int flag[],int size)
{
?for (int i = 0; i < size; i++)
? if (flag[i]==1)
? ?cout << i+1 << ' ';
?cout << endl;
}

bool Equal(int flag[],const int size,int sum)
{
?for (int i = 0; i < size; i++)
? if (flag[i] == 1)
? ?sum = sum-(i + 1);
?if (sum == 0)
? return true;
?return false;
}

void Find(int n, int m,int flag[],const int size,const int sum)
{
?if (n >= 1)
?{
? flag[n - 1] = 1;
? Find(n - 1, m - n, flag,size,sum);
? flag[n - 1] = 0;
? Find(n - 1, m,flag, size,sum);
?}
?else
?{
? if (Equal(flag, size,sum))
? ?Out(flag, size);
?}

}

void? main()
{
?int n, m;
?cin >> n >> m;
?int *flag = new int[n];
?Find(n, m, flag, n,m);
?system("pause");
}