Subset Problem -- Any Materials?

Question

Yes this is a homework/lab assignment. I am interesting in coming up with/finding an algorithm (I can comprehend :P) for using "backtracking" to solve the subset sum problem.

Anyone have some helpful resources? I've spent the last hour or so Googling with not much like finding something I think I could actually use. xD

Thanks SO!

Answer 1

Put the data in a vector.

Then write a routine that has 3 arguments: the vector, an index, and a sum. Call this routine with the following arguments: the vector, 0, 0.

The routine should do the following tasks:

• check if we reached the end of the vector (index==size). If this is the case, we can return immediately.
• call itself with arguments: the vector, index+1, sum+vector[index] (in this case we add the element at the index to the sum and continue with the vector)
• call itself with arguments: the vector, index+1, sum (in this case we don't add the element at the index to the sum, but still continue)

I deliberately left out 2 parts in this algorithm:

• first, you should check the sum at some point. If it is zero, then you found a correct subset
• second, you should also pass knowledge about which elements you used, so if the sum is zero, you can print out the subset. Consider using an STL::set for this.

Alternatively, you can use the return value of the function to determine whether a correct subset has already been found or not.

The complexity of the algorithm is O(2^N) so it will be very slow for big sets.

Have fun.