1 条题解

  • 0
    @ 2026-2-6 17:19:13
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    
    // [1] 全局变量:n为输入的整数总个数,c为需要凑出的目标子集和
    ll  n,c;
    // [2] 全局数组:存储输入的n个整数(下标从1开始,符合输入顺序)
    ll arr[8000];
    // [3] 全局向量:记录DFS过程中当前选中的数(即当前子集路径)
    vector<ll> dp;
    // [4] 全局标记:1表示未找到和为c的子集,0表示已找到(找到后终止所有递归)
    int flag=1;
    
    // [10] 自定义DFS函数:按输入顺序遍历数,尝试选/不选当前数,寻找和为c的子集
    // 参数x:当前遍历到的数的索引(从1开始);参数sum:当前已选数的累加和
    void dfs(ll x,ll sum){
        // [11] 递归终止条件:已找到解/遍历完所有数/当前和超过目标和,直接返回
    	if(flag==0 || x >n || sum>c) return;
    	
    	// [12] 计算“选择当前数arr[x]”后的累加和
    	ll ans=sum+arr[x];
    	// [13] 选择当前数:将其加入当前路径(子集)
    	dp.push_back(arr[x]);
    	
    	// [14] 找到目标解:选择当前数后累加和等于c
    	if(ans == c){
    		// [15] 输出当前路径中的所有数(即满足条件的子集)
    		for(int i=0;i<dp.size();i++){
    			cout<<dp[i]<<" ";
    		}
    		// [16] 标记为已找到解,后续递归会直接终止
    		flag=0;
    		// [17] 终止当前递归分支
    		return;
    	}
    	
    	// [18] 递归遍历下一个数:选择当前数的情况下,继续寻找
    	dfs(x+1,ans);
    	
    	// [19] 回溯操作:不选择当前数,从路径中移除
    	dp.pop_back();
    	// [20] 递归遍历下一个数:不选择当前数的情况下,继续寻找
    	dfs(x+1,sum);
    }
    
    // [5] 主函数:程序入口,处理输入、提前判断、启动DFS、输出结果
    int main(){
        // [6] 输入:读取整数个数n和目标子集和c
        cin>>n>>c;
        // [7] 定义变量ans:存储所有输入数的总和,用于提前判断无解情况
        ll ans=0;
        // [8] 循环读取n个整数,存入数组并累加总和
        for(int i=1;i<=n;i++)
        {
        	cin>>arr[i];   // 读取第i个整数,存入arr[i]
        	ans+=arr[i];   // 累加计算所有数的总和
    	}
        
        // [9] 提前判断:若所有数的总和小于目标和c,必然无解,直接输出提示并退出
        if(ans<c){
        	cout<<"No Solution!";
        	return 0;
    	}
        
        // [21] 启动DFS:从第1个数开始遍历,初始累加和为0
        dfs(1,0);
        
        // [22] DFS结束后仍未找到解,输出无解提示
        if(flag==1)
    	{
        	cout<<"No Solution!";
    	}
        // [23] 主函数正常退出
        return 0;
    }
    

    信息

    ID
    1278
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者