DFS + Backtracking + Pruning ..

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int n, m, s, id, k, x;

vector<int> path;
vector<vector<int>> ans;

void dfs( vector<vector<int>>& g, vector<int>& w, int cur, int sum) {

  path.emplace_back(w[cur]);
  sum += w[cur];

  // 题目给定了权重都是正整数。这里是个剪枝！！！
  if (sum > s) return; // prunning
  if (g[cur].empty()) { // leaf node
    if (sum == s) ans.emplace_back(path);
    return;
  }
  for (const auto& child : g[cur])  {
    dfs(g, w, child, sum);
    path.pop_back(); // backtracking 
  }
}

void printAns() {
  sort(rbegin(ans), rend(ans));
  for (const auto& p : ans) {
    for (int i = 0; i < p.size(); ++i) {
      printf("%d", p[i]);
      if (i < p.size() - 1) putchar(' ');
    }
    putchar('\n');
  }
}

// debug helper function
void printGraph(vector<vector<int>>& g) {
  for (int i = 0; i < g.size(); ++i) {
    printf("%d: [", i);
    for (int j = 0; j < g[i].size(); ++j) printf("%d ", g[i][j]);
    printf("]\n");
  }
}

int main(void) {
  cin >> n >> m >> s;
  vector<int> w(n);
  for (int i = 0; i < n; ++i) cin >> w[i];

  vector<vector<int>> g(n);
  while (m--) {
    cin >> id >> k;
    for (int i = 0; i < k; ++i) {
      cin >> x;
      g[id].emplace_back(x);
    }
  }

  // printGraph(g);
  dfs(g, w, 0, 0);
  printAns();

  return 0;
}