蓝桥杯 砝码称重 dp/dfs

题目链接：

https://www.lanqiao.cn/problems/1447/learning/?subject_code=1&group_code=4&match_num=12&match_flow=1&origin=cup

思想：dfs暴力枚举过一半的分

代码：

#include
using namespace std;
#define int long long
const int N = 5e6+5;
int n,w[N];
bool st[N];
int res;
//表示k个砝码，重量是sum
void dfs(int k,int sum){
	if(k>n){
		if(sum>0&&!st[sum]){
			res++;
			st[sum]=true;
			
		}
		return;
	}
	dfs(k+1,sum-w[k]);  //放右边
	dfs(k+1,sum);  //不选
	dfs(k+1,sum+w[k]);   //放左边
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
    
    cin>>n;
    for(int i=1;i>w[i];
    }
    dfs(0,0);
    cout