Write an algorithm which is given an integer, 1 <= N <= 1066, produces a list weightPositions. An item in the list weightPositions, is L if the corresponding weight is only in the left pan. It is R if the corresponding weight is only in the right pan, and it is O if the corresponding weight is in neither pan or in both pans. For example, if left…

BalanceN.cpp

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <map>
#include <fstream>

using namespace std;
vector<int> x;
struct pan {
    vector<int> left;
    vector<int> right;
    pan(vector<int> l, vector<int> r): left(l), right(r){}   
};

void findallans(int i, int j, int sumi, int sumj, vector<int> li, vector<int> lj, map<int, vector<pan>> &ans){
    // i is for left
    // j is for right
    int diff = sumj-sumi;
    vector<int> li2(li);
    vector<int> lj2(lj);

    if( diff >= 0){
        // create a pan object
        pan p(li,lj);
        // save it here
        ans[diff].push_back(p);
    }

    if (i >= x.size())
        return;
    
    li2.push_back(x[i]);
    lj2.push_back(x[j]);

    findallans(i+1,j+1, sumi, sumj+x[j], li, lj2, ans);
    findallans(i+1,j+1, sumi+x[i], sumj, li2, lj, ans);
    findallans(i+1,j+1, sumi+x[i], sumj+x[j], li2, lj2, ans);
    findallans(i+1,j+1, sumi, sumj, li, lj, ans);
}


void findN(int i, int j, int sumi, int sumj, vector<int> li, vector<int> lj, map<int, vector<pan>> *ans, int N){
    // i is for left
    // j is for right
    int diff = sumj-sumi;
    vector<int> li2(li);
    vector<int> lj2(lj);
    
    // if theres a solution already, stop
    if( (*ans).size() > 0 ) return;

    // found what we're looking for
    if( diff == N){
        // create a pan object
        pan p(li,lj);
        // save it here
        (*ans)[diff].push_back(p);
        return;
    }

    // if we're over the limit
    if (i >= x.size())
        return;
    
    // create two new lists
    li2.push_back(x[i]);
    lj2.push_back(x[j]);

    // 
    // Recursion. This is also depth first search.
    findN(i+1,j+1, sumi, sumj+x[j], li, lj2, ans, N);
    findN(i+1,j+1, sumi+x[i], sumj, li2, lj, ans, N);
    findN(i+1,j+1, sumi+x[i], sumj+x[j], li2, lj2, ans, N);
    findN(i+1,j+1, sumi, sumj, li, lj, ans, N);
}

void print_ans(map<int, vector<pan>> &ans, ofstream &f, int position){
    // print the ans data structure
    for(auto i = ans[position].begin(); i != ans[position].end(); ++i){
        f << "[" << " ";
        for(auto j = (*i).left.begin();j != (*i).left.end(); ++j){
            f << *j << " ";
        }
        f << "]" << "  [ ";
        for(auto j = (*i).right.begin();j != (*i).right.end(); ++j){
            f << *j << " ";
        }
        f << "]" << " " << endl;
    }
}

int main(){
    map<int, vector<pan>> ans;
     map<int, vector<pan>> *forN = new map<int,vector<pan>>();
    int d[] = {1,3,9,27,81,243,729};
    x = vector<int>(begin(d), end(d));
    ofstream f;
    f.open("ans.txt");
    for ( int i = 1; i < 1067; ++i){
        findN(0,0,0,0,vector<int>(), vector<int>(), forN, i);
        f << i << ": ";
        cout<< i << ": ";
        print_ans(*forN, f, i);        
        forN = new map<int,vector<pan>>();               
    }
    f.close();
    cout << "done" << endl;
    std::cin.get();
    return 0;
}