中興面試題：簡單的背包問題的兩種思路

問題描述：

輸入兩個整數n 和m，從數列1，2，3.......n 中隨意取幾個數,
使其和等於 m ,要求將其中所有的可能組合列出來。這是一個簡單的背包問題

算法：

有一些分析認為此題有兩種思路：遞歸和非遞歸。

但是我覺得“是否遞歸”只是形式上的區別，用來代表兩種思路有點牽強。

我認為應該從算法的處理過程來區分：

第一種：檢查所有的組合，去掉和不為m的組合。直觀地可將算法分成兩步①產生所有子集②挑選符合要求的子集

第二種：構造組合，在產生組合的過程中檢測組合的合法性，若發現已不可能構造出合法組合，則停止操作。（如組合中已有元素的和已大於m，則不再繼續）

打個不太准確的比喻：就像一棵樹，第一種是先生成樹，再對葉節點（生成的結果）進行挑選。第二種是在生成樹的過程中，及時剪掉不合法的枝，只產生合法的葉節點。

對於第一種先求子集的思路，算法過程比較清晰，我在這篇博文裡謝了三種產生子集的方法http://blog.csdn.net/hgqqtql/article/details/39744051檢驗挑選的比較簡單，不在給出代碼了。

算法實現：

第二種思路的遞歸實現：

#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");
}