首页 > 代码库 > IT公司100题-1-二叉树转换为双链表

IT公司100题-1-二叉树转换为双链表

2024-07-18 05:23:21   213人阅读

问题描述：
输入两个整数n 和m，从数列1，2，3，…，n 中随意取几个数, 使其和等于m，将所有可能的组合都打印出来。
 
分析：
利用递归的思路，对于1，2，3，…，n 中的任意一个数，要么选，要么不选。递归下去，直到其和等于m时，输出。
 

解答：

 

 1 // 21.cc 2 #include <iostream> 3 #include <cstring> 4 using namespace std; 5  6 void print(int* aux, int n) { 7     for (int i = 0; i < n; i++) 8         if (aux[i]) 9             cout << i << " ";10     cout << endl;11 }12 13 void helper(int m, int cur, int* aux, int n) {14     if (m == 0)15         print(aux, n);16     if (m <= 0 || cur == n)17         return;18 19     // 不选cur20     helper(m, cur + 1, aux, n);21 22     // 选cur23     aux[cur] = 1;24     helper(m - cur, cur + 1, aux, n);25     aux[cur] = 0;  // 回溯26 }27 28 void find_combi(int n, int m) {29     if (n > m) 30         find_combi(m, m);31 32     int* aux = new int[n];  // aux[i] = 1，表示选择i33     memset(aux, 0, n * sizeof(int));34     helper(m, 0, aux, n);35 }36 37 int main() {38     int n, m;39     cout << "input n and m:" << endl;40     cin >> n >> m;41     find_combi(n, m);42     return 0;43 }

 

$ ./a.exeinput n and m:6 31 20 1 231 20 30 1 2

 

 


联系
我们