遞歸求排列和組合（無重復和有重復）

給定一個大小為n的數組，輸出所有全排列。

1、數組中無重復元素：從前到後，依次將數組中的元素放置在輸出數組中，若放完就輸出，然後遞歸的改變元素的位置，直到輸出所有的全排列。遞歸中使用一個標記數組來記錄某個元素是否已經被放置過。

2、數組中有重復元素：這個和1比較類似，區別在於用一個標記數組記錄某個元素的次數，每放置一次就減一。

問題1的代碼如下：

void PermRecur(vector<int>& ivec, vector<int>& use, vector<int>& res, int k)
{
	//如果下標k等於size，說明所有元素已經放置完畢
	if (k == ivec.size())
	{
		for (int i = 0; i < k; ++i)
			cout << res[i] << ' ';
		cout << endl;
		return;
	}
	for (int i = 0; i < ivec.size(); ++i)
	{
		//標記為0表示沒有被放置過
		if (use[i] == 0)
		{
			//元素被放置後將標記賦為1
			use[i] = 1;
			res[k] = ivec[i];
			PermRecur(ivec, use, res, k + 1);
			//遞歸結束後再將該元素的標記賦為0
			use[i] = 0;
		}
	}
}

void Perm(vector<int>& ivec)
{
	int size = ivec.size();
	assert(size > 0);
	//所有元素的標記為初始化為0
	vector<int> use(size);
	vector<int> res(size);
	PermRecur(ivec, use, res, 0);
}
void main()
{
	int a[] = {1, 2, 3};
	vector<int> ivec(a, a + 3);
	Perm(ivec);
}

#include <iostream>
#include <vector>
#include <assert.h>
using namespace std;

void PermRecur(vector<int>& num, vector<int>& use, vector<int>& res, int k)
{
	//如果下標k等於size，說明所有元素已經放置完畢
	if (k == res.size())
	{
		for (int i = 0; i < k; ++i)
			cout << res[i] << ' ';
		cout << endl;
		return;
	}
	for (int i = 0; i < num.size(); ++i)
	{
		//標記大於0說明還有剩余的元素沒有放置
		if (use[i] > 0)
		{
			//元素被放置後次數減1
			--use[i];
			res[k] = num[i];
			PermRecur(num, use, res, k + 1);
			//遞歸結束後再將該元素的次數加1
			++use[i];
		}
	}
}

void Perm(vector<int>& ivec)
{
	assert(!ivec.empty());
	int size = ivec.size();
	vector<int> res(size);
	vector<int> use;
	vector<int> num;
	//根據ivec統計每個元素的出現次數，並將去重後的所有元素存在num中
	use.push_back(1);
	num.push_back(ivec[0]);
	for (int i = 1; i < size; ++i)
	{
		int j = 0;
		for (; j < i; ++j)
		{
			if (ivec[i] == ivec[j])
			{
				++use[j];
				break;
			}
		}
		if (j == i)
		{
			use.push_back(1);
			num.push_back(ivec[i]);
		}
	}
	PermRecur(num, use, res, 0);
}

void main()
{
	int a[] = {1, 2, 2};
	vector<int> ivec(a, a + 3);
	Perm(ivec);
}

給定一個大小為n的數組，輸出所有的子集。子問題是從n個元素中選擇m個元素，然後循環調用即可。

1、數組中無重復的元素：從前到後依次將數組中的元素放置到輸出數組中，當元素個數達到m時輸出即可。然後進行遞歸，將剩余的元素和m個元素進行交換。

2、數組中有重復的元素：和全排列類似，先去重並計算元素的次數，然後進行遞歸。

問題1的代碼如下：

#include <iostream>
#include <vector>
#include <assert.h>
using namespace std;

void CombRecur(vector<int>& ivec, vector<int>& res, int m, int begin, int k)
{
	//當k等於m的時候輸出結果
	if (k == m)
	{
		for (int i = 0; i < res.size(); ++i)
			cout << res[i] << ' ';
		cout << endl;
		return;
	}
	for (int i = begin; i < ivec.size(); ++i)
	{
		res[k] = ivec[i];
		CombRecur(ivec, res, m, i + 1, k + 1);
	}
}

void Comb(vector<int>& ivec)
{
	assert(!ivec.empty());
	for (int i = 1; i <= ivec.size(); ++i)
	{
		vector<int> res(i);
		CombRecur(ivec, res, i, 0, 0);
	}
}

void main()
{
	int a[] = {1, 2, 3};
	vector<int> ivec(a, a + 3);
	Comb(ivec);
}

#include <iostream>
#include <vector>
#include <assert.h>
using namespace std;

void CombRecur(vector<int>& num, vector<int>& use, vector<int>& res, 
			   int m, int begin, int k)
{
	//當k等於m時，說明已經選夠m個元素
	if (k == m)
	{
		for (int i = 0; i < res.size(); ++i)
			cout << res[i] << ' ';
		cout << endl;
		return;
	}
	for (int i = begin; i < num.size(); ++i)
	{
		//如果元素次數大於0就選擇
		if (use[i] > 0)
		{
			//選擇之後就將元素次數減1
			--use[i];
			res[k] = num[i];
			//這裡遞歸的時候begin仍然是i，因為第i個元素有可能重復
			CombRecur(num, use, res, m, i, k + 1);
			++use[i];
		}
	}
}

void Comb(vector<int>& ivec)
{
	assert(!ivec.empty());
	int size = ivec.size();
	vector<int> num;
	vector<int> use;
	//根據ivec統計每個元素的出現次數，並將去重後的所有元素存在num中
	num.push_back(ivec[0]);
	use.push_back(1);
	for (int i = 1; i < size; ++i)
	{
		int j = 0;
		for (; j < i; ++j)
		{
			if (ivec[i] == ivec[j])
			{
				++use[j];
				break;
			}
		}
		if (j == i)
		{
			use.push_back(1);
			num.push_back(ivec[i]);
		}
	}
	//從1~n循環調用即可求出大小為1~n的所有子集
	for (int i = 1; i <= size; ++i)
	{
		vector<int> res(i);
		CombRecur(num, use, res, i, 0, 0);
	}
}

void main()
{
	int a[] = {1, 2, 2};
	vector<int> ivec(a, a + 3);
	Comb(ivec);
}