（转载）数组a[]={3,5,2,4,1,8}，要求从a中找出所有“和”等于10的子集

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

背包问题。
不过就这道题目本身而言，由于集合a中只要6个元素，而不是成千上万，所以可以使用更直观的办法：
只要你能通过程序给出数组a中元素所组成的集合的所有的子集合（幂集），那么只需在这些集合中搜索等于10的就可以了。

而6个元素构成的集合的幂集可以通过6位二进制数来表示，对于从0到2的6次方减1（63）之间的所有的数，让其每一位比特位代表一个元素，当该位为0时
表示该数所表示的子集中没有这个元素，否则表示拥有这个元素，这样就能对应出所有的组合，然后在这些所有的组合中检测和是否为10就可以了。

#include <stdio.h> #define ARRAY_SIZE 6
#define MAX_NUM (1<<ARRAY_SIZE)
int main()
{
int i, j;
int sum;
int a[ARRAY_SIZE] = {,,,,,};
int count = ; for(i = ; i < MAX_NUM; i++)
{
sum = ;
for(j = ; j < ARRAY_SIZE; j++)
{
if(i & ( << j))
sum += a[j];
} if( == sum)
{
printf("%d: ", ++count);
for(j = ; j < ARRAY_SIZE; j++)
{
if(i & ( << j))
printf("%d + ", a[j]);
}
printf("\b\b= 10.\n");
}
}
printf("\nTotal: %d.\n", count); return ;
}