July面试整理系列--（5）

编程求解：
输入两个整数 n 和 m，从数列1，2，3.......n 中随意取几个数,
使其和等于 m ,要求将其中所有的可能组合列出来.

 1 #include <iostream>
 2 #include <vector>
 3 #include <stack>
 4 
 5 using namespace std;
 6 
 7 /*
 8 思路：
 9 h（n，m）表示从1到n中 任意取几个数和为m的方法数。
10 则有 h（n，m）=   h（n-1，m-n） 或者  h（n-1，m）     （既n取或者不取）
11 当然其中  注意到 当 m < n 时 可以 直接跳到 h(m,m).还要注意边界条件，既当满足什么条件是
12 可以直接得出结果。
13 
14 递归深搜
15 */
16 stack<int> ans;
17 void fun(int n,int m)
18 {
19     if(n >= 0 && m == 0)
20     {
21         stack<int> ans_tmp = ans;
22         while(!ans_tmp.empty())
23         {
24             cout<<ans_tmp.top()<<" ";
25             ans_tmp.pop();
26         }
27         cout<<endl;
28         return;
29     }
30     if(n == 1 && m == 1)
31     {
32         ans.push(1);
33         stack<int> ans_tmp = ans;
34         while(!ans_tmp.empty())
35         {
36             cout<<ans_tmp.top()<<" ";
37             ans_tmp.pop();
38         }
39         cout<<endl;
40         ans.pop();
41         return;
42     }
43     if(n == 1 && m > 1)
44     {
45         return;
46     }
47     if(n <= m)
48     {
49         ans.push(n);
50         fun(n-1,m-n);
51         ans.pop();
52 
53         fun(n-1,m);
54     }
55     else
56     {
57         fun(m,m);
58     }
59     return;
60 }
61 
62 int main()
63 {
64     fun(10,7);
65     return 0;
66 }