Does this algorithm actually work? Sum of subsets backtracking algorithm

Question

I want to know if this backtracking algorithm actually works.

In the text book Foundations of Algorithms, 5^th edition, it is defined as follows:

Algorithm 5.4: The Backtracking Algorithm for the Sum-of-Subsets Problem

Problem: Given n positive integers (weights) and a positive integer W, determine all combinations of the integers that sum up to W.

Inputs: positvie integer n, sorted (nondecreasing order) array of positive integers w indexed from 1 to n, and a positive integer W.

Outputs: all combinations of the integers that sum to W.

void sum_of_subsets(index i, 
                    int weight, int total)  {
  if (promising(i))
     if (weight == W)
        cout << include[1] through include [i];
     else {
        include[i + 1] = "yes";               // Include w[i + 1].
        sum_of_subsets(i + 1, weight + w[i + 1], total - w[i + 1]);
        include[i + 1] = "no";                // Do not include w[i + 1].
        sum_of_subsets(i + 1, weight, total - w[i + 1]);
     }
}

bool promising (index i);  {
  return (weight + total >= W) && (weight == W || weight + w[i + 1] <= W);
}

Following our usual convention, n, w, W, and include are not inputs to our routines. If these variables were defined globally, the top-level call to sum_of_subsets would be as follows:

sum_of_subsets(0, 0, total);

At the end of chapter 5, exercise 13 asks:

13. Use the Backtracking algorithm for the Sum-of-Subsets problem (Algorithm 5.4) to find all combinations of the following numbers that sum to W = 52:

    w1 = 2     w2 = 10     w3 = 13     w4 = 17     w5 = 22     w6 = 42

I've implemented this exact algorithm, accounting for arrays that start at 1 and it just does not work...

 void sos(int i, int weight, int total) {
    int yes = 1;
    int no = 0;

    if (promising(i, weight, total)) {
        if (weight == W) {
            for (int j = 0; j < arraySize; j++) {
                std::cout << include[j] << " ";
            }
            std::cout << "\n";
        }
        else if(i < arraySize) {
            include[i+1] = yes;
            sos(i + 1, weight + w[i+1], total - w[i+1]);
            include[i+1] = no;
            sos(i + 1, weight, total - w[i+1]);
        }
    }
}


int promising(int i,  int weight, int total) {
    return (weight + total >= W) && (weight == W || weight + w[i+1] <= W);
}   

I believe the problem is here:

sos(i + 1, weight, total - w[i+1]);
sum_of_subsets(i+1, weight, total-w[i+1]);

When you reach this line you are not backtracking correctly.

Is anyone able to identify a problem with this algorithm or actually code it to work?

Answer 1

I personally find the algorithm problematic. There is no bounds checking, it uses a lot of globals, and it assumes an array is indexed from 1. I don't think you can copy it verbatim. It's pseudocode for the actual implementation. In C++ arrays always start from 0. So you're likely to have problems when you try do include[i+1] and you are only checking i < arraySize.

The algorithm also assumes you have a global variable called total, which is used by the function promising.

I have reworked the code a bit, putting it inside a class, and simplified it somewhat:

class Solution
{
private:
    vector<int> w;
    vector<int> include;

public:
    Solution(vector<int> weights) : w(std::move(weights)),
        include(w.size(), 0) {}

    void sos(int i, int weight, int total) {
        int yes = 1;
        int no = 0;
        int arraySize = include.size();

        if (weight == total) {
            for (int j = 0; j < arraySize; j++) {
                if (include[j]) {
                    std::cout << w[j] << " ";
                }
            }
            std::cout << "\n";
        }
        else if (i < arraySize)
        {
            include[i] = yes;
            //Include this weight
            sos(i + 1, weight + w[i], total);
            include[i] = no;
            //Exclude this weight
            sos(i + 1, weight, total);
        }
    }
};

int main()
{   
    Solution solution({ 2, 10, 13, 17, 22, 42 });
    solution.sos(0, 0, 52);
    //prints:    10 42
    //           13 17 22
}

Answer 2

So yes, as others pointed out, you stumbled over the 1 based array index.

That aside, I think you should ask the author for a partial return of the money you paid for the book, because the logic of his code is overly complicated.

One good way not to run into bounds problems is to not use C++ (expecting hail of downvotes for this lol).

There are only 3 cases to test for:

• The candidate value is greater than what is remaining. (busted)
• The candidate value is exactly what is remaining.
• The candidate value is less than what is remaining.

The promising function tries to express that and then the result of that function is re-tested again in the main function sos.

But it could look as simple as this:

search :: [Int] -> Int -> [Int] -> [[Int]]
search (x1:xs) t path 
    | x1 > t = []
    | x1 == t = [x1 : path]
    | x1 < t = search xs (t-x1) (x1 : path) ++ search xs t path
search [] 0 path = [path]
search [] _ _ = []


items = [2, 10, 13, 17, 22, 42] :: [Int]
target = 52 :: Int

search items target []
-- [[42,10],[22,17,13]]

Now, it is by no means impossible to achieve a similar safety net while writing C++ code. But it takes determination and a conscious decision on what you are willing to cope with and what not. And you need to be willing to type a few more lines to accomplish what the 10 lines of Haskell do.

First off, I was bothered by all the complexity of indexing and range checking in the original C++ code. If we look at our Haskell code (which works with lists), it is confirmed that we do not need random access at all. We only ever look at the start of the remaining items. And we append a value to the path (in Haskell we append to the front because speed) and eventually we append a found combination to the result set. With that in mind, bothering with indices is kind of over the top.

Secondly, I rather like the way the search function looks - showing the 3 crucial tests without any noise surrounding them. My C++ version should strive to be as pretty.

Also, global variables are so 1980 - we won't have that. And tucking those "globals" into a class to hide them a bit is so 1995. We won't have that either.

And here it is! The "safer" C++ implementation. And prettier... um... well some of you might disagree ;)

#include <cstdint>
#include <vector>
#include <iostream>

using Items_t = std::vector<int32_t>;
using Result_t = std::vector<Items_t>;

// The C++ way of saying: deriving(Show)
template <class T>
std::ostream& operator <<(std::ostream& os, const std::vector<T>& value) 
{
    bool first = true;
    os << "[";
    for( const auto item : value) 
    {
        if(first) 
        {
            os << item;
            first = false;
        }
        else
        {
            os << "," << item;
        }
    }
    os << "]";
    return os;
}

// So we can do easy switch statement instead of chain of ifs.
enum class Comp : int8_t 
{   LT = -1
,   EQ = 0
,   GT = 1
};

static inline 
auto compI32( int32_t left, int32_t right ) -> Comp
{
    if(left == right) return Comp::EQ;
    if(left < right) return Comp::LT;
    return Comp::GT;
}

// So we can avoid index insanity and out of bounds problems.
template <class T>
struct VecRange
{
    using Iter_t = typename std::vector<T>::const_iterator;
    Iter_t current;
    Iter_t end;
    VecRange(const std::vector<T>& v)
        : current{v.cbegin()}
        , end{v.cend()}
    {}
    VecRange(Iter_t cur, Iter_t fin)
        : current{cur}
        , end{fin}
    {}
    static bool exhausted (const VecRange<T>&);
    static VecRange<T> next(const VecRange<T>&);
};

template <class T>
bool VecRange<T>::exhausted(const VecRange<T>& range)
{
    return range.current == range.end;
}

template <class T>
VecRange<T> VecRange<T>::next(const VecRange<T>& range)
{
    if(range.current != range.end)
        return VecRange<T>( range.current + 1, range.end );
    return range;   
}

using ItemsRange = VecRange<Items_t::value_type>;


static void search( const ItemsRange items, int32_t target, Items_t path, Result_t& result)
{
    if(ItemsRange::exhausted(items))
    {
        if(0 == target)
        {
            result.push_back(path);
        }
        return;
    }

    switch(compI32(*items.current,target))
    {
        case Comp::GT: 
            return;
        case Comp::EQ:
            {
                path.push_back(*items.current);
                result.push_back(path);
            }
            return;
        case Comp::LT:
            {
                auto path1 = path; // hope this makes a real copy...
                path1.push_back(*items.current);
                search(ItemsRange::next(items), target - *items.current, path1, result);
                search(ItemsRange::next(items), target, path, result);
            }
            return;
    }
}

int main(int argc, const char* argv[])
{
    Items_t items{ 2, 10, 13, 17, 22, 42 };
    Result_t result;
    int32_t target = 52;

    std::cout << "Input: "  << items << std::endl;
    std::cout << "Target: " << target << std::endl;
    search(ItemsRange{items}, target, Items_t{}, result);
    std::cout << "Output: " << result << std::endl;
    return 0;
}

Answer 3

The code implements the algorithm correctly, except that you did not apply the one-based array logic in your output loop. Change:

for (int j = 0; j < arraySize; j++) {
    std::cout << include[j] << " ";
}

to:

for (int j = 0; j < arraySize; j++) {
    std::cout << include[j+1] << " ";
}

Depending on how you organised your code, make sure that promising is defined when sos is defined.

See it run on repl.it. Output:

0 1 0 0 0 1
0 0 1 1 1 0

The algorithm works fine: the second and third argument to the sos function act as a window in which the running sum should stay, and the promising function verifies against this window. Any value outside this window will be either to small (even if all remaining values were added to it, it will still be less than the target value), or too great (already overrunning the target). These two constraints are explained in the beginning of chapter 5.4 in the book.

At each index there are two possible choices: either include the value in the sum, or don't. The value at includes[i+1] represents this choice, and both are attempted. When there is a match deep down such recursing attempt, all these choices (0 or 1) will be output. Otherwise they are just ignored and switched to the opposite choice in a second attempt.