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?

  • $\begingroup$ When you say you're not "too familiar", do you know what backtracking is? $\endgroup$ – Christopher Carl Heckman Mar 8 '16 at 23:39
  • $\begingroup$ I've heard of problems about it (The queen problem) but no I don't understand the general gist of it (in such a scope). Would you like me to rephrase parts of my question? $\endgroup$ – TTEd Mar 8 '16 at 23:42
  • $\begingroup$ You need to read up on it then. I'll give a partial solution below, anyway. And tacktracking is like brute force, but stops once it becomes obvious that you can't complete your partial solution. $\endgroup$ – Christopher Carl Heckman Mar 8 '16 at 23:49
  • $\begingroup$ (1) Apparently you mean subsets of positive integers. (2) Sets of positive integers that add up to $w$ are called partitions of $w$ (see this article), and when the number of summands $k$ is fixed we call them partitions with exactly $k$ parts. $\endgroup$ – hardmath Mar 9 '16 at 2:59

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.

  • $\begingroup$ So how many solutions are there? $\endgroup$ – TTEd Mar 9 '16 at 0:10
  • $\begingroup$ Nevermind I found the last one which would be (10,11) $\endgroup$ – TTEd Mar 9 '16 at 0:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.