0
8.0kviews
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

1 Answer
0
631views

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

Please log in to add an answer.