Question: Solve the following sum of subset problem using backtracking: w= {1, 3, 4, 5}, m=8. Find the possible subsets of 'w' that sum to 'm'.

Subject: Analysis Of Algorithm

Topic: Backtracking

Difficulty: High

aoa(14) • 1.5k views
modified 20 months ago  • written 22 months ago by gravatar for satishmanje93 satishmanje9320

Subset sum problem is to find subset of elements that are selected from a given set whose sum adds up to a given number K. We are considering the set contains non-negative values. It is assumed that the input set is unique (no duplicates are presented).

Using exhaustive search we consider all subsets irrespective of whether they satisfy given constraints or not. Backtracking can be used to make a systematic consideration of the elements to be selected.

Assume given set of 4 elements, say w[1] … w[4]. Tree diagrams can be used to design backtracking algorithms. The following tree diagram depicts approach of generating variable sized tuple. enter image description here

written 20 months ago by gravatar for satishmanje93 satishmanje9320
Please log in to add an answer.