首页 > 代码库 > Combinations

Combinations

2024-07-22 03:29:47   210人阅读

组合数，这题的关键是不能漏解。第一感觉应该是分治法。

这里，为了方便叙述，使用一个辅助函数

vector<vector<int>> combhelper(int first, int last, int k)；

含义是从first 到last（左闭右开）的区间中选择K个数的组合数，我们倒过来看，最后一个数(last - 1)或者包括在内，或者不包括在内。

这样就把问题规模递减了。具体代码如下：

vector<vector<int>> combhelper(int first, int last, int k){	vector<vector<int>> result;	if (k == 1){		for (int i = first; i != last; i++){			vector<int> vi;			vi.push_back(i);			result.push_back(vi);		}		return result;	}	if (last <= first) return result;	if (last - first == k){		vector<int> vk;		for (int i = first; i != last; i++)			vk.push_back(i);		result.push_back(vk);		return result;	}	vector<vector<int>> r1 = combhelper(first, last - 1, k - 1);	for (auto it = r1.begin(); it != r1.end(); it++){		it->push_back(last - 1);	}	vector<vector<int>> r2 = combhelper(first, last - 1, k);	for (auto it = r2.begin(); it != r2.end(); it++)		result.push_back(*it);	for (auto it = r1.begin(); it != r1.end(); it++)		result.push_back(*it);	return result;}vector<vector<int> > combine(int n, int k){	vector<vector<int>> result = combhelper(1, n + 1, k);	return result;}

　　这里说明针对边界和特殊情形的处理。combhepler向下递归有两条路，一是

combhelper(first, last - 1, k - 1);
  二是：
combhelper(first, last - 1, k);
对于第一种情况，可知，当last - first一直不变，所以只能一直递减，显然k == 1属于分界。
对于第二种情况，last - first可以减小到k，这样也返回了。

Combinations


联系
我们