Design and Analysis of Algorithms20825 marksNumerical: Subset sum backtrackingBacktracking Algorithms
Find all possible subsets of the integers that sum to 21 in the array {5, 6, 10, 11, 15} using back tracking technique.
Find all possible subsets of the integers that sum to 21 in the array {5, 6, 10, 11, 15} using back tracking technique. [5]
- Set of integers: $W = {5, 6, 10, 11, 15}$ (already in ascending order) - Number of elements: $n = 5$ - Target sum: $M = 21$ Goal: find all subsets whose elements sum to exactly $21$. --- For the sum-of-subsets backtracking algorithm, keep track of: - $s$ = sum of elements included so far -