Careercup

2014-05-02 02:28

原题：

I/P: N, k 

O/P: all subset of N with exactly K elements. 

eg: I/p: N = 5, K =3 
O/p: 

1 2 3 
1 2 4 
1 2 5 
1 3 4 
1 3 5 
2 3 4 
2 3 5 
3 4 5

题目：从N个数中选K个，输出所有选法。

解法：递归解决。

代码：

 1 // http://www.careercup.com/question?id=6204973461274624
 2 #include <vector>
 3 using namespace std;
 4 
 5 class Solution {
 6 public:
 7     void findKSubsets(int n, int k, vector<vector<int> > &result) {
 8         if (n <= 0) {
 9             return;
10         }
11         if (k < 1 || k > n) {
12             return;
13         }
14         
15         vector<int> subset;
16         
17         DFS(0, 0, subset, result, n, k);
18     }
19 private:
20     void DFS(int in, int ik, vector<int> &subset, 
21              vector<vector<int> > &result, 
22              const int &n, const int &k) {
23         if (ik == k) {
24             result.push_back(subset);
25             return;
26         }
27         
28         int i;
29         for (i = in + 1; i <= n - (k - ik) + 1; ++i) {
30             subset.push_back(i);
31             DFS(i, ik + 1, subset, result, n, k);
32             subset.pop_back();
33         }
34     };
35 };
36 
37 int main()
38 {
39     vector<vector<int> > result;
40     int n, k;
41     int i, j;
42     Solution sol;
43     
44     while (scanf("%d%d", &n, &k) == 2 && (n > 0 && k > 0)) {
45         sol.findKSubsets(n, k, result);
46         printf("{
");
47         for (i = 0; i < (int)result.size(); ++i) {
48             printf("    {");
49             for (j = 0; j < (int)result[i].size(); ++j) {
50                 printf((j ? ", %d" : "%d"), result[i][j]);
51             }
52             printf("}
");
53         }
54         printf("}
");
55         
56         for (i = 0; i < (int)result.size(); ++i) {
57             result[i].clear();
58         }
59         result.clear();
60     }
61     
62     return 0;
63 }