Solution for a programming problem from unknown contest

connectedSticks.cpp

#include <bits/stdc++.h>
using namespace std;

// Assume that you have N sticks with different lengths
// You can connect these sticks to get a composed stick of some length
// You are given a targetLenth, is it possible to get a composed stick of this length?

// For this solution I represent problem a s graph where a vertex is marked by the mask (every bit says which of the sticks
// we have already chosen) and the length of edges are the length of the corresponding sticks.
// For instance, if we have lengths=[2,3,5], than 0th vertex corresponds to the case when we haven't picked up a stick yet, 
// it's neighbors are the vertices with 1 
// on the corresponding position (001, 010, 100) and the path to them from 0th vertex is the length of the sticks (2,3,5)). etc
// Than I just use BFS and mark vertices I have visited. During this search I avoid visiting vertices which have been visited and 
// those which are too far from the root

bool canComposeStick(vector<int>& lengths, int targetLength) {
    queue< pair<int, int> > q;
    unordered_set<int> visited;
    // add vertices which correspond to just one from lengths
    for (int i = 0; i < lengths.size(); ++i) {
        q.push( make_pair(1<<i, lengths[i]) );
    }

    while (!q.empty()) {
        auto v = q.front(); q.pop();
        if (v.second == targetLength)
            return true;
        if (v.second > targetLength || visited.find(v.first) != visited.end())
            continue;

        visited.insert(v.first);
        for (int i = 0; i < lengths.size(); ++i) {
            int m = 1<<i;
            if ((m & v.first) == 0) { // not taken yet
                q.push( make_pair(m | v.first, v.second + lengths[i]) );
            }
        }

    }
    return false;
}


int main(int, char**) {
    vector<int> length = {2,5,7,8};
    int x = 11; // assume x < sum lengths so it is possible to do it

    cout << canComposeStick(length, x) << "\n";

    return 0;
}