Proficient.
Put your skills to the test.

Problem summary

Place all n distinct weights on a balance, choosing one unused weight and one pan at each move. At every intermediate step, the left pan must be no heavier than the right. Count the complete ordered placement sequences.

Constraints

1 ≤ n ≤ 9; 1 ≤ each weight < 1000.

Worked example

Original statement sample.

3
1 2 4

15

Solution analysis

1. For each weight there are three states: unused, on the right, or on the left. Encode these states as ternary digits of one integer. There are only 3^n≤19683 assignments, much fewer than all n!·2^n ordered histories.
2. Let solve(state,balance,placed) count legal continuations, where balance is right weight minus left weight. Choose any unused weight. Placing it right is always safe; placing it left is safe exactly when balance is at least that weight. When all weights are placed, one complete continuation has been found.
3. Memoize by the ternary state alone. Its digits uniquely determine both the current balance and the number already placed, so different legal histories reaching the same state have the same available continuations. Adding their continuation counts still preserves the fact that histories are different.
4. For [1,2,4], if 4 is placed right first, each order of the other two weights allows all four side choices, giving 8 sequences. Starting with 2 on the right gives 4, and starting with 1 on the right gives 3, for a total of 15. An upper bound on any answer is 9!·2^9=185794560, so int is sufficient.

Why it works

Every legal continuation starts by choosing exactly one unused weight and its side. The two branch conditions accept precisely the moves preserving nonnegative balance. These choices are disjoint, and the recursive base counts each completed history once. Memoization reuses only identical future-choice problems, so it does not merge or lose different histories.

Watch out. The restriction applies after every move, not just at the end. The first weight must go right. Counting only final pan partitions loses placement orders. Ternary encoding must distinguish left from right.

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
using namespace std;
int n;
vector<int>weight,powerOfThree,memo;
int countWays(int state,int balance,int placed){
    if(placed==n){
        return 1;
    }
    int&result=memo[state];
    if(result!=-1){
        return result;
    }
    result=0;
    for(int i=0;i<n;i++){
        if((state/powerOfThree[i])%3!=0){
            continue;
        }
        // Ternary digit 1 means right, digit 2 means left.
        result+=countWays(state+powerOfThree[i],balance+weight[i],placed+1);
        if(balance>=weight[i]){
            result+=countWays(state+2*powerOfThree[i],balance-weight[i],placed+1);
        }
    }
    return result;
}
int main(){
    cin>>n;
    weight.resize(n);
    for(int&value:weight){
        cin>>value;
    }
    powerOfThree.resize(n+1,1);
    for(int i=1;i<=n;i++){
        powerOfThree[i]=3*powerOfThree[i-1];
    }
    memo.assign(powerOfThree[n],-1);
    cout<<countWays(0,0,0)<<'\n';
}