written 6.7 years ago by | modified 2.7 years ago by |

**Subject:** Analysis Of Algorithm

**Topic:** Backtracking

**Difficulty:** High

**1 Answer**

0

8.6kviews

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'.

written 6.7 years ago by | modified 2.7 years ago by |

**Subject:** Analysis Of Algorithm

**Topic:** Backtracking

**Difficulty:** High

ADD COMMENT
EDIT

0

671views

written 6.5 years ago by |

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.

ADD COMMENT
EDIT

Please log in to add an answer.