【算法】枚举子集

问题描述：输入n, 表示集合S的元素个数，输入m表示S的子集元素个数，然后枚举元素个数为m的S集合子集的所有可能

e.g. 输入n=5，m=3，即求集合S={1,2,3,4,5}所有元素为3的子集，{1,2,3}、{1,2,4}、{1,2,5}、{1,3,4}、{1,3,5}、{1,4,5}、{2,3,4}、{2,3,5}、{2,4,5}、{3,4,5};

从中可以发现一些规律：按顺序枚举，每次循环，找到最右下标为index的元素value，满足 value < (n - (m - 1 - index)), 然后标记position=index，position这个位置的元素增加1，若position < m-1，则后面的元素都等于前一个元素加1.

 1 /*
 2 *Copyright: CheerM
 3 *Author: CheerM
 4 *Date: 2016-11-03
 5 *Description: 输入n, 表示集合S的元素个数，输入m表示S的子集元素个数，然后枚举元素个数为m的S集合子集的所有可能
 6 */
 7 
 8 #ifndef _002_H_
 9 #define _002_H_
10 #include <iostream>
11 
12 using namespace std;
13 
14 /*打印子集*/
15 void print(int* subset, int m) {
16     cout << "{ " << subset[0];
17     for (int i = 1; i < m; i++)
18         cout << ", " << subset[i];
19     cout << " }" << endl;
20 }
21 
22 /*
23 *Function:       printSubSet
24 *Description:    输入n, 表示集合S的元素个数，输入m表示S的子集元素个数，然后枚举元素个数为m的S集合子集的所有可能
25 *Input:          n,表示集合S的大小
26 *                 m,表示子集的大小
27 *Output:         枚举每个子集，并且输出
28 *Return:         None
29 */
30 void printSubSet(int n, int m) {
31     if (m > n) cout << "n should be larger than m" << endl;
32 
33     /*初始化集合S*/
34     int* s = new int[n];
35     for (int i = 0; i < n; i++) s[i] = i + 1;
36 
37     /*标记要增加1的位置*/
38     int position;
39     int* subset = new int[m];/*子集*/
40     for (int i = 0; i < m; i++) subset[i] = s[i];/*初始化子集*/
41     print(subset, m);
42     while (1) {
43         if (subset[0] == n - m + 1 && subset[m - 1] == n)break;
44 
45         /*找到subset中满足<n-(m-1-index)的最右元素坐标*/
46         for (int i = m - 1; i >= 0; i--)
47             if (subset[i] < (n - (m - 1 - i))) {
48                 position = i;
49                 subset[position]++;
50                 break;
51             }
52 
53         /*顺序初始化后面的元素，随index增加，递增1*/
54         for (int i = position + 1; i < m; i++)
55             subset[i] = subset[i - 1] + 1;
56 
57         print(subset, m);
58     }
59 
60 }
61 
62 
63 #endif

002.h

测试结果：