学步园

问题描述：对给定集合A和整数K，求出A的所有和等于K的子集（可以包括其本身），如A = {10, 20, 30, 40, 50, 60}且K = 60，则满足条件的子集有{10, 20, 30}, {10, 50}, {20, 40}, {60}

思路1：利用二进制法枚举子集，再找出满足条件的子集。此方法优点是思想简单，缺点是枚举本身效率不高

代码：

void process(int a[], int n, int k){  //k为所要求的和
	assert(a != NULL);
	assert(n > 0);

	for(int i = 1; i < (1<<n); i++){
		int sum = 0;  //sum用于计算当前子集的和
		for(int j = 0; j < n; j++)
			if((i>>j)&0x01 == 0x01) sum += a[j];
		if(sum == k){
			for(int j = 0; j < n; j++)
				if((i>>j)&0x01 == 0x01) printf("%d ", a[j]);
			printf("\n");
		}
	}
}

思路2：使用回溯法对枚举的子集进行有效剪枝。仍是“开关“思路，每一个元素都有”子集中存在“和”子集中不存在“两种取值，对这两种分支进行递归，可得2^n种情况（实际上应为2^n-1，因为空集必然不符合本题要求）。递归过程中，当前要求的和sum以及候选元素集合均不断减小。若sum == 0则表示找到这样的子集，输出；若sum
> 0则表示仍要在候选元素集合中选取元素；若sum < 0，说明当前子集和已超过题目要求，此分支无效（这是该算法的一个剪枝），该分支不再继续递归下去（此剪枝必须基于给定集合的元素是升序排列的）

代码：

void process(int a[], int n, int sum, int b[], int k){  //sum为当前所要求的和，b[]数组用于记录所求子集，k表示当前分支扫描到a[k]
	if(sum == 0){  //找到满足条件的子集
		for(int i = 0; i < k; i++)
			if(b[i] == 1) printf("%d ", a[i]);
		printf("\n");
	}
	else if(sum > 0 && n > 0){  //需要继续找，隐含了对sum < 0 || n < 0的剪枝
		b[k] = 1;  //当前元素a[k]在子集中的情况
		process(a, n-1, sum-a[k], b, k+1);
		b[k] = 0;  //当前元素a[k]不在子集中的情况
		process(a, n-1, sum, b, k+1);
	}
}

注意：

1.main函数调用方法是：

process(a, n, sum, b, 0);  //从a[0]开始扫描分支

2.思考为什么问题的每一个解都能正确输出b[]而不影响其他解（1. b[k]决定递归线路；2. 回溯对b[]覆盖）