some.cpp

#include <iostream>
#include <vector>
#include <set>
#include <boost/iterator/counting_iterator.hpp>
#include <algorithm>
#include <functional>

typedef std::vector<int>    int_vec;
typedef std::set<int>       int_set;

std::ostream& operator<<(std::ostream& out, const int_vec& vec)
{
    out << "[";
    for (int i = 0; i < vec.size() - 1; ++i)
    {
        out << vec[i] << ",";
    }
    out << vec[vec.size() - 1] << "]";
    return out;
}

std::ostream& operator<<(std::ostream& out, const int_set& set)
{
    out << "{";
    for (auto it = set.begin(); it != set.end(); ++it)
    {
        out << *it << ";";
    }
    out << "}";
    return out;
}

void loop(int level, int_vec& vec, const int_set& elem_set, const int_set& dist_set)
{
    //for (int i = 0; i < level; ++i) std::cout<<"\t";
    //std::cout<<"loop("<<level<<","/*<<vec<<","*/<<elem_set<<","<<dist_set<<")\n";
    if (level == vec.size())
    {
        std::cout << vec << "\n";
        return;
    }
    auto parent_index = (level + 1) / 2 - 1;
    auto parent_value = vec[parent_index];
    auto left_value = level % 2 ? 0 : vec[level - 1];
    std::for_each(elem_set.begin(), elem_set.end(), [&](int elem)
            {
                auto parent_dist = abs(parent_value - elem);
                if ((elem > left_value) && (dist_set.find(parent_dist) != dist_set.end()))
                {
                    vec[level] = elem;
                    int_set new_elem_set(elem_set);
                    int_set new_dist_set(dist_set);
                    new_elem_set.erase(elem);
                    new_dist_set.erase(parent_dist);
                    loop(level + 1, vec, new_elem_set, new_dist_set);
                }
            });
}

void solution(int_vec& vec)
{
    auto len = vec.size();
    auto values_end = std::find_if(vec.begin(), vec.end(), [](int x) { return x == 0; });
    auto values_count = std::distance(vec.begin(), values_end);
    int_set elem_used(vec.begin(), values_end);
    int_set elem_set;
    std::set_difference(boost::counting_iterator<int>(1),
                        boost::counting_iterator<int>(len+1),
                        elem_used.begin(),
                        elem_used.end(),
                        std::inserter(elem_set, elem_set.end()));
    int_set dist_set(boost::counting_iterator<int>(1),
                     boost::counting_iterator<int>(len));
    for (int i = 1; i < values_count; ++i)
    {
        dist_set.erase(abs(vec[(i+1) / 2 - 1] - vec[i]));
    }
    loop(values_count, vec, elem_set, dist_set);
}

void build_arr(int_vec& vec, int count, int depth)
{
    auto len = (1 << depth) - 1;
    vec.resize(len);
    vec[0] = len;
  
  std::function<void (int, const int_set&, const int_set&)> loop = [&](int level, const int_set& elem_set, const int_set& dist_set)
  {
        if (level == count) return;
        auto parent_index = (level + 1) / 2 - 1;
        auto parent_value = vec[parent_index];
        int max_elem = 0;
        int max_dist = 0;
        std::for_each(elem_set.begin(), elem_set.end(), [&](int elem)
                {
                    int parent_dist = abs(parent_value - elem);
                    if (dist_set.find(parent_dist) != dist_set.end() && max_dist < parent_dist)
                    {
                        max_elem = elem;
                        max_dist = parent_dist;
                    }
                });
        vec[level] = max_elem;
        int_set new_elem_set(elem_set);
        int_set new_dist_set(dist_set);
        new_elem_set.erase(max_elem);
        new_dist_set.erase(max_dist);
        loop(level + 1, new_elem_set, new_dist_set);
        
  };
  
  int_set elem_set(boost::counting_iterator<int>(1),
                   boost::counting_iterator<int>(len));
  int_set dist_set(boost::counting_iterator<int>(1),
                   boost::counting_iterator<int>(len));
  loop(1, elem_set, dist_set);
}

int main()
{
    int_vec vec;
    build_arr(vec, 2, 4);
    solution(vec);
}