两个思路-深搜求所有子集、组合

思路1：深搜求排列、组合，每次递归选取一个没有使用的元素加入。排列：顺序不同为不同排列，因此每次从第一个元素开始判断选取。组合：顺序无关，为规避重复方案，每次从上一次选取元素的后一个元素开始选取。

#include<bits/stdc++.h>
using namespace std;
int a[35], n, box[35];
long long ans;
void dfs(int id, int num){
	for(int i=0; i<id; i++) ans+=box[i];  //对于每一个子集，将子集元素累加到ans上
	for(int i=num; i<n; i++){ //为规避重复方案，不从第一个元素开始选取
		box[id]=a[i];
		dfs(id+1, i+1);
	}
}
int main() {
	while(cin>>a[n]){
		n++;
	}
	dfs(0, 0);
    cout<<ans;
	return 0;
}

思路2：组合，观察可知，原数组中的所有元素，在所有子集中出现的总次数是相同的，因此如果可以求出这个次数，则次数乘以所有元素的和，即为所有子集元素之和。

子集：包含 1个元素、2个元素、...、n个元素
某个元素出现的次数即包含某个元素的子集个数。
包含某个元素的子集：即除这个元素外，另外选部分元素组成子集。C(n-1, 0)+C(n-1, 1)+C(n-1, 2)+...+C(n-1, n-1)

#include<bits/stdc++.h>
using namespace std;
long long c[35][35]={1};
void init(){
	for(int i=0; i<=30; i++){
		for(int j=0; j<=i; j++){
			if(j==0 || j==i) c[i][j]=1;
			else c[i][j]=c[i-1][j-1]+c[i-1][j];
		}
	}
}
long long n,a[35], sum, ans;
int main() {
	init();
	while(cin>>a[n]){
		sum+=a[n];
		n++;
	}
    //计算所有子集中某个元素出现的次数
    //子集：包含 1个元素、2个元素、...、n个元素
    //包含某个元素的子集：即除这个元素外，另外选部分元素组成子集
    //C(n-1, 0)+C(n-1, 1)+C(n-1, 2)+...+C(n-1, n-1)
	for(int i=0; i<n; i++){
		ans+=c[n-1][i];
	}
    //所有元素都出现了ans次，则所有子集元素之和为sum*ans
    cout<<sum*ans;
	return 0;
}