I'm asked to use the backtracking algorithm to determine all the subsets of integers whose sum is equal to 'w'(Lower case)
In this case I'm given that:
where a set of postive n integers W(Capitalized)
$n =5 $
$W = \{5,6,10,11,16\}$
$w = 21$
I've been reading ahead in my course work and came to this problem, however, I'm not so sure how to approach it, I'm not too familiar with the "backtracking algorithm" yet.
I'm guessing that there is a brute force way to approach this, however, I don't believe the back tracking algorithm involves brute force. Any ideas?
Best Answer
The problem was to find all subsets of $W = \{5,6,10,11,16\}$ which add up to $21$, using backtracking.
First, the elements of $W$ are sorted.
So we start with the solutions $A$ that contain $5$; $A=\{5\}$ for now.
Now, it's possible that $6\in A$, so we now search for solutions which contain $5$ and $6$; $A=\{5,6\}$.
Now, it's possible that $10\in A$, so we now search for solutions which contain $5$, $6$, and $10$; $A=\{5,6,10\}$.
We now have a solution! Output it.
Now for the backtracking: Remove the last number we added ($10$); now $A=\{5,6\}$.
Now what if $10\not\in A$? Add the next number, $11$, so $A=\{5,6,11\}$.
Now the sum of the elements of $A$ is too big (it's $22$), so remove $11$ to make $A=\{5,6\}$. In fact, we don't even need to check $16$, where the sum will be even bigger.
Now we backtrack another step; we remove the $6$ to make $A=\{5\}$ again.
Now, add the next-larger number $10$: $A=\{5,10\}$.
Now, add the next-larger number $11$: $A=\{5,10,11\}$.
Oops, the sum is too big. Remove $11$, and don't bother checking $16$. Now $A=\{5,10\}$.
This takes care of solutions with $\{5,10\}$. Now remove the $10$ to make $A=\{5\}$ again.
Now add the number after $11$: $A=\{5,16\}$.
Solution! Output it.
Now remove the $16$, so $A=\{5\}$.
There are no numbers bigger than $16$, so we backtrack yet again and remove the $5$; $A=\emptyset$.
Now we start again by adding $6$ to $A$ ($A=\{6\}$) and then try adding $10$, $11$, and $16$ in various combinations.
Later on, the algorithm will pick up the last solution.