Skip to content
doubtly

1 answer

Solutions: {3, 8, 9}, {5, 7, 8} and {5, 15}, i.e. x = (1,0,0,1,1,0), (0,1,1,1,0,0) and (0,1,0,0,0,1).

Given \(n = 6\), \(W = \{3, 5, 7, 8, 9, 15\}\) (already in ascending order), \(M = 20\). Total \(r = 3+5+7+8+9+15 = 47\).

Approach (backtracking): decide for each weight in order whether to include it (\(x_k = 1\)) or not (\(x_k = 0\)). Keep \(s\) = sum of chosen weights and \(r\) = sum of the remaining weights. A node is killed (bounded) if

  • \(s + w_{k+1} > M\) (even the next smallest weight overshoots), or
  • \(s + r < M\) (even taking all remaining weights cannot reach M).

Tracing the search (depth first, include before exclude):

  • 3, 5, 7 → s = 15; adding 8 gives 23 > 20, killed. 3, 5, 8 → 16; 3, 5, 9 → 17; next weight overshoots. Dead ends.
  • 3, 7, 8 → 18; 3, 7, 9 → 19: dead ends.
  • 3, 8, 9 → s = 20 = M. Solution 1: {3, 8, 9}.
  • Exclude 3: 5, 7, 8 → s = 20. Solution 2: {5, 7, 8}.
  • 5, 15 → s = 20. Solution 3: {5, 15}.
  • Excluding both 3 and 5: the remaining weights {7, 8, 9, 15} have no subset with sum 20, so the search ends.

Algorithm (initial call SumOfSub(0, 1, 47), with weights sorted and \(w_1 \le M\)):

SumOfSub(s, k, r):
  // s = sum of w[1..k-1] chosen, r = w[k] + ... + w[n]
  x[k] = 1                        // left child: include w[k]
  if s + w[k] == M:
      print x[1..k]               // a subset found
  else if s + w[k] + w[k+1] <= M:
      SumOfSub(s + w[k], k + 1, r - w[k])
  // right child: exclude w[k]
  if (s + r - w[k] >= M) and (s + w[k+1] <= M):
      x[k] = 0
      SumOfSub(s, k + 1, r - w[k])

Check: 3 + 8 + 9 = 20, 5 + 7 + 8 = 20, 5 + 15 = 20. Worst-case time is \(O(2^{n})\), but bounding prunes most of the state-space tree.

Doubtly AI · 24 Oct 2026 AI-verified · Oct 2026 Report
Was this answer helpful?

Your answer

Log in or create a free account to answer this question.