学步园

在实际编程时，有时会遇到这样的问题 ，我们需要列举出某个数组中所有可能的组合？比如，有这样的题目，有一个数组，我们可以从其中选择任意数量的数字，问问最后能够得到多少可能的和？

如数组A[5] = {1,2,3,4,5};

则从A中选取数字有以下情形：

1   2    3    4     5

1 2   = 3

1 3  = 4

1 4  = 5

1 5 = 6

2 3 = 5

2 4 =6

2 5 = 7

3 4 =7

3 5 = 8

4 5 =9

1 2 3 = 6               1 24 = 7              1 2 5 = 8     1 3 4 = 8  1 3 5 = 9            1  4 5 = 10

2  3 4 = 9         2  3 5 = 10             2  4  5 = 11     3  4 5 = 12

1 2 3 4 = 10   1 2 3 5 = 11    1 2 4  5 = 12   1 3  4  5 = 13   2 3 4 5 = 14   

1  2     3   4   5 = 15

程序实现如下：

#include <vector>
using namespace std;

vector< vector<int> > AllSeries; //所有可能的序列

void GetPartSeries(int nDataNum, vector<int> left, vector<int> right)
{
 if (left.size() == nDataNum)
 {
  AllSeries.push_back(left);
  return;
 }

 for (vector<int>::iterator iter = right.begin(); iter != right.end(); iter ++)
 {
  vector<int> newleft(left);
  newleft.push_back(*iter);

  vector<int> newright;

  for (vector<int>::iterator i = iter + 1; i != right.end(); i ++)
  {
   newright.push_back(*i);
  }
  GetPartSeries(nDataNum,newleft,newright);

 }
}
int main()
{
 int nDataNum = 5;
 vector<int> Left;
 vector<int> Right;
 for (int i = 0; i < 5; i ++)
 {
  Right.push_back(i+2);
 }
 GetPartSeries(5,Left,Right);
 GetPartSeries(4,Left,Right);
 GetPartSeries(3,Left,Right);
 GetPartSeries(2,Left,Right);
 GetPartSeries(1,Left,Right);

 for (vector< vector<int> >::iterator iter = AllSeries.begin(); iter != AllSeries.end(); iter ++)
 {
  vector<int> temp = *iter;

  for (vector<int>::iterator i = temp.begin(); i != temp.end(); i ++)
  {
   printf("%d   ",*i);
  }
  printf("/n");
 }
 return 0;
}