解法一、DFS

🔹 剪枝

當 sum+nums[i] > m 時，因為數組經過排序
所以之後的 sum+nums[i] 都會比 m 大
也就不用試了，直接 break

✅ 完整代碼

評分結果(參考) ： AC (0.4s, 336KB)

#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<int> nums;
vector<int> ans;
bool haveSol = false;

void dfs(int sum, int i){
    if(i>n) return;

    if(sum == m){
        haveSol = true;
        for(int j=0; j<ans.size(); j++){
            if(j != 0) cout << " ";
            cout << ans[j];
        }
        cout << "\n";
        return;
    }
    
    for(; i<n; i++){
        if(sum+nums[i] > m) break;
        
        ans.push_back(nums[i]);
        dfs(sum+nums[i], i+1);
        ans.pop_back();
    }
}

int main(){
    ios::sync_with_stdio(false); 
    cin.tie(nullptr);
    
    cin >> n >> m;
    
    nums.resize(n);
    
    for(int& i : nums) cin >> i;
    sort(nums.begin(), nums.end());

    dfs(0, 0);
    if(!haveSol) cout << "-1";

    return 0;
}