1 问题

从n个元素中挑选m个元素，有多少组组合，可以重复选择。

输入：3 3

输出：10

解析：从三个元素中选取三个元素，可以重复选，共有多少组组合。111 112 113 122 123 133 222 223 233 333 一共十组组合，注：121 112 211是同一种组合，不能重复计算。

2 分析

如果采用递归，必然包含大量的重复计算，运算复杂度呈指数级别增长，肯定超时。

用二维数组进行分析，先枚举一定范围内的结果。arr[i][j]表示从i个元素中选取m个元素，所有组合数。

arr[i][1] = i，从i个元素中选取1个元素，可组成i个组合。

arr[1][j] = 1，从1个元素中选取j个元素，可组成一个组合。

arr[2][2] = 3，11 22 12 三种组合。

arr[4][2] = 10，从4个元素中选取2个元素，11 22 33 44 12 13 14 22 23 24 34 共有10种组合。

arr[2][4] = 4，从2个元素中选取4个元素，1111 2222 1122 1222 1112 共有4种组合。

。。。

观察上面二维表，不难发现规律，arr[i][j] = arr[i][j-1] + arr[i-1][j-1]，就是当前元素的值等于左边的值加上上面的值，比如arr[4][4] = 25 = 15 + 20 = arr[4][3] + arr[3][3]。

所以此题建立一个二维数组，然后遍历整个二维数组，计算相应的值即可。

出于对空间复杂度的考虑，当每一行计算完成之后，只为下一次计算提供服务，除此之外再也没有用到，造成了大量的空间浪费，因此，可用一维滚动数组来解决。

如果算第i行第j列，就相当于第j列，arr[j] = arr[j-1] + arr[j]，此时arr[j]被更新。以行i为外层循环，arr[1] = i，然后arr[j] = arr[j-1] + arr[j]。

3 代码

#include <iostream>
using namespace std;

void test() {
	int n, m;
	cin >> n >> m;    //从n中选取m个元素
					  //为了方便，角标从1开始，所以多申请一个空间
	int* arr = new int[m + 1];
	for (int i = 0; i <= m; i++)    //全部初始化为1
		arr[i] = 1;
	for (int i = 2; i <= n; i++) {
		arr[1] = i;              //第一个初始化为i
		for (int j = 2; j <= m; j++) {
			arr[j] = arr[j - 1] + arr[j];    //更新arr[j]		
		}
	}
	cout << arr[m] << endl;
}

int main() {
	test();
	system("pause");
	return 0;
}

4 打印所有组合

这个时间复杂度会很高，遍历所有可能，暂时没有想到更好的办法。

//这个主要参考了yysdsyl的博客

#include <vector>
#include <iostream>
#include <iterator>
using namespace std;

void mycom(int* arr, int n, int m, vector<int>& brr,int& sum) {
	//递归终止条件
	if (m == 1) {		//从n种元素中选1个元素，组合有n种
		sum += n;
		for (int i = 0; i < n; i++) {
			//copy(brr.begin(), brr.end(), ostream_iterator<int>(cout));
			for (int j = 0; j < brr.size(); j++)
				cout << brr[j];
			cout << arr[i];
			cout << endl;
		}
		return;
	}
	//递归终止条件
	if (n == 1) {		//从1种元素中选取m个元素，一共有一种
		sum++;
		for (int i = 0; i < brr.size(); i++)
			cout << brr[i];
		for (int i = 0; i < m; i++)
			cout << *arr;
		cout << endl;
		return;
	}
	brr.push_back(arr[0]);
	mycom(arr, n, m - 1, brr, sum);		//递归两种情况
	brr.pop_back();
	//规模减小
	mycom(arr+1, n - 1, m, brr, sum);		//递归两种情况
}

void test() {
	int n, m;
	cin >> n >> m;
	int sum = 0;
	vector<int> brr;
	int* arr = new int[n];
	for (int i = 0; i < n; i++)
		arr[i] = i + 1;
	mycom(arr, n, m, brr, sum);
	cout << endl;
	cout << sum << endl;
}

int main() {
	test();
	system("pause");
	return 0;
}