前言

上一篇博客中，我们求10个数的排列问题中，如果不需要输出全排列，而是输出组合，即子集（子集内部的元素是没有顺序的），那么该如何做呢？

从以前我们所学的知识中，一个包含n个元素的集合，它的子集有2^n个。
用二进制的概念进行对照是最直观的
例如n=3的集合{a1，a2，a3}，它的子集和二进制的对应关系如下

空集：0 0 0
a1:  1 0 0
a2:  0 1 0
a3:  0 0 1
.
.
.
a1,a2,a3:1 1 1  

所以，每个子集对应一个二进制数，这个二进制数的每一个都对应这个子集中的某个元素，而且子集中的元素是没有顺序的。

从上面的对应表也可以理解为什么子集的数量是2^n个，因为所有二进制数的总个数是2 ^n。

案例1：打印n位二进制数的所有子集

源码

#include<iostream>
using namespace std;

void print_subset(int n) {
	for (int i = 0; i < (1 << n ); i++) {//所以一共就是2^n个子集
		//i:0 ~ 2^n，，每个i的二进制数都对应一个子集，一次打印一个子集，最后得到所有子集
		for (int j = 0; j <n; j++) {//将1和i的n位中的每一位做与运算，逐个检查
			if (i & (1 << j)) {
				cout <<"1 ";
			}
			else {
				cout << "0 ";
			}
		}
		cout << endl;
	}
}
int main() {
	int n;
	cout << "n:";
	cin >> n;
	print_subset(n);
	system("pause");
	return 0;
}

运行结果

分析

回到上一篇博客的问题3

题目

打印n个数中任意m个数的组合。

思路

对照子集生成的二进制方法，已经知道一个子集对应一个二进制数。那么一个有k个元素的子集，它对应的二进制数中有k个1。所以，问题就转化为查找1的个数为k的二进制数，这些二进制数，就是需要打印的子集。

那么如何判断二进制数中1的个数为k，这里和大家分享一个新方法，就是每次消除最后一个1 公式： kk=kk & (kk-1)。每经过一次这样的与运算，原始数据就少一个1.
如1011

1011 & （1011-1）=1010； 少一个1
1010 & （1010-1）=1000；再少一个1
1000 & （1000-1）=0000； 又少一个1

所以三次操作下来，结果为0，那么原来的数值就有3个1.

源码

#include<iostream>
using namespace std;

//第一步就是生成n个数的所有子集
void print_set(int n, int m) {//
	for (int i = 0; i < (1 << n); i++) {//生成所有子集数
		int num = 0;
		int k = i;
		while (k) {  //第二步，获取1的个数
			k &= (k - 1);
			num++;
		}
		if (num == m) {//如果有m个1，就是一个组合
			for (int j = 0; j < n; j++) {//将这个结果i的每一位答应出来
				if (i & (1 << j)) {
					cout << "1 ";
				}
				else {
					cout << "0 ";
				}
			}
		}
		cout << endl;
	}
}

int main() {
	int n, m;
	cout << "n m:";
	cin >> n >> m;
	print_set(n, m);
	system("pause");
	return 0;
}

运行结果

分析

总结

排列和组合的区别就是，排列是有序的，组合是无序的
1 2 3， 3 2 1对组合是一样的，对排列就不一样。

同时大家记住这个找1的个数方法哦，在很多时候，用起来都是很好的。

下一篇博客我们分析 BFS（广度优先算法）和队列