整数拆分

将一个整数拆分成不重复的整数之和。

example：

6 = 1 + 5 = 1 + 2 + 3
= 2 + 4

采用递归方法实现。

 1 #include <iostream>   
 2 #include <vector>   
 3 using namespace std;   
 4 
 5 /**
 6     6 = 1 + 5 = 1 + 2 + 3
 7       = 2 + 4
 8 **/   
 9 
10 void split( int n, int s, vector<int>  ret)   
11 {   
12     // 递归结束条件   
13     if ( n <= 2*s)   
14     {   
15         vector<int>::iterator iter;   
16         ret.push_back(n);   
17         //注意打印的位置：递归结束时   
18         for ( iter = ret.begin(); iter != ret.end(); iter++ )
19         {
20             cout << *iter << '\t';
21         }
22         cout << endl;
23     }
24 
25     for ( int i = s; i < (n+1)/2; i++ )    
26     {
27         // pop 上一分支的数据
28         if ( i != s)
29             ret.pop_back();
30         ret.push_back(i);    
31         split(n-i, i+1, ret);
32     }
33 }
34 
35 int main(int argc, char** argv)
36 {
37     vector<int> ret;
38     int n = 20;
39     split(n,1, ret);
40     return 0;
41 }

View Code