Counting paths between 3 cities in C++ The task is to make a program that prints out how many possible paths a driver can use to visit three cities so that he visits each city exactly n times. The program must be executed within 1 minute and print the solution for n = 10. The program works correctly but for n above 7 it doesn't execute in time. Is there a way to get it to execute n=10 in time? These are some of the solutions: n = 1, the solution is 6, n = 2, the solution is 30, n = 3, the solution is 174 and n = 4, the solution is 1092.

#include&lt;iostream&gt;
#include &lt;algorithm&gt;
using namespace std;
double paths (long long unsigned int path[],int n,double s,int e){
    int r=0;
    do{
        for(int i=0;i&lt;e-1;i++){
            if(path[i]!=path[i+1]){
                r++;
            }
        }
            if(r==e-1){
                s++;

            }
            r=0;

        }while(next_permutation(path, (path+e)));

        return s;
    }
int main(){
    double s=0;
    int y=0;
    int buff=0;
    int n;
    cin&gt;&gt;n;
    int e=(n*3);
    long long unsigned int path[e];
    while(y!=e){
       for(int t=1;t&lt;=3;t++){
           path[y]=t;
           y++;
       }
    };
    bool test=false;
    for(int z=0;z&lt;e;z++){
        for (int j =0; j&lt;e; j++){
            if (path[j+1] &lt; path[j]){
                buff=path[j];
                path[j]=path[j+1];
                path[j+1]=buff;
                test=true;
            }
        }
        if(!test){
            break;
        }else{
            test=false;
        }
    }
    cout&lt;&lt;"Number of posibilities: "&lt;&lt;paths(path,n,s,e)&lt;&lt;endl;

}
Simply modifying this algorithm will not solve the problem in the required time. When n=10, this code is going through every permutation of an array of 30 integers. That is 30! (about 2^107) permutations. Going faster through the loop in paths() will not be enough.

I would suggest a backtracking solution, which cuts down the search space enormously. I think the answer when n=10 should be around 125,000,000. I'd also claim the code should run in under 30 seconds.

Obligatory code review comment. In the loop in main(), there is an out of bounds bug when evaluating buff[j+1] when j == e-1;

Here is the code that I wrote using a backtracking approach.

#include&lt;iostream&gt;
#include &lt;utility&gt;
#include &lt;vector&gt;
#include &lt;map&gt;
using namespace std;

class TripCounter {
public:
    TripCounter(int cities, int visits) : length(cities*visits) {
        for (auto i = 1; i &lt;= cities; i++)
            pool[i] = visits;
    }

    long Count() {
        count = 0;
        BackTracker(0);
        return count;
    }

private:
    void BackTracker(int level) {
        if (level == length) {
            count++;
            return;
        }
        for (auto&amp; bucket : pool) {
            if (IsValidAtLevel(bucket, level)) {
                trip.push_back(bucket.first);
                bucket.second--;
                BackTracker(level + 1);
                bucket.second++;
                trip.erase(trip.end() - 1);
            }
        }
    }

    bool IsValidAtLevel(pair&lt;int, int&gt; bucket, int level) {
        if (bucket.second == 0)
            return false;
        if (level == 0)
            return true;
        if (bucket.first == trip[level - 1])
            return false;
        return true;
    }

private:
    map&lt;int, int&gt; pool;
    int const length = 0;
    vector&lt;int&gt; trip;
    int count = 0;
};

int main() {
    int n;
    cin &gt;&gt; n;

    auto counter = TripCounter(3, n);
    cout &lt;&lt; "Backtracking: " &lt;&lt; counter.Count() &lt;&lt; endl;
}