问题:
2010年中兴面试题
编程求解:
输入两个整数 n 和 m,从数列1,2,3…….n 中 随意取几个数,
使其和等于 m ,要求将其中所有的可能组合列出来.
思路:
类似这种组合问题一般都是使用递归的策略,考虑到n个数和为m,假设要解决的函数为f(n,m), 假设我们选择了第n个数,那么问题就变成了f(n-1,m-n),
否则的话问题就是f(n-1,m), 再考虑下边界条件: 如果n<1 或者 m<1显然不会有结果, 如果n==m,那么显然可以输出一个结果了,然后问题就变成了f(m-1,m)
所以初步写的代码如下:
vector<int> queueV;
void findSum(int n, int m)
{
if(n< || m<)
return;
if(m==n)
{
vector<int>::iterator it;
for(it = queueV.begin(); it!=queueV.end(); ++it)
{
cout << *it << ' ';
}
cout << m << endl;
n = m-; //从剩下的1~m-1中寻找值为m的数列
}
queueV.push_back(n);
findSum(n-, m-n);
queueV.pop_back();
findSum(n-, m);
}
不过这个代码涉及到了很多可以避免的压栈出栈和递归等操作,会浪费比较多的时间,所以优化的版本如下:
vector<int> queueV;
void findSum2(int n, int m)
{
if(n< || m<)
return;
if(m>n)
{
queueV.push_back(n);
findSum(n-, m-n);
queueV.pop_back();
findSum(n-, m);
}
else
{
vector<int>::iterator it;
for(it = queueV.begin(); it!=queueV.end(); ++it)
{
cout << *it << ' ';
}
cout << m << endl;
findSum(m-, m);
}
}