Repository: TheAlgorithms/C-Plus-Plus
File: bit_manipulation/travelling_salesman_using_bit_manipulation.cpp (C++)

Code before:
        std::uint64_t n, // n is the no of cities we have.
        std::vector<std::vector<uint32_t>> &dp) //dp is taken to memorize the state to avoid recomputition
{
    //base case;
    if (setOfCities == (1 << n) - 1) // we have covered all the cities
        return dist[city][0]; //return the cost from the current city to the original city.

    if (dp[setOfCities][city] != -1)
        return dp[setOfCities][city];
    //otherwise try all possible options
    uint64_t ans = 2147483647 ;
    for (int choice = 0; choice < n; choice++) {
        //check if the city is visited or not.
        if ((setOfCities & (1 << choice)) == 0 ) { // this means that this perticular city is not visited.
            std::uint64_t subProb = dist[city][choice] + travelling_salesman_using_bit_manipulation(dist, setOfCities | (1 << choice), choice, n, dp);
            // Here we are doing a recursive call to tsp with the updated set of city/node
            // and choice which tells that where we are currently.
            ans = std::min(ans, subProb);
        }

    }
    dp[setOfCities][city] = ans;
    return ans;
}
}
}



/**
 * @brief Self-test implementations
 * @returns void
 */
static void test() {
    //Testcase 1
    std::vector<std::vector<uint32_t>> dist = {
        {0, 20, 42, 35}, {20, 0, 30, 34}, {42, 30, 0, 12}, {35, 34, 12, 0}
    };
    uint32_t V = dist.size();
    std::vector<std::vector<uint32_t>> dp(1 << V, std::vector<uint32_t>(V, -1));
    assert(bit_manipulation::travelling_salesman_using_bit_manipulation::travelling_salesman_using_bit_manipulation(dist, 1, 0, V, dp) == 97);
    std::cout << "Testcase 1 Passed" << "\n";

    //TestCase 2;
    dist = {{0, 5, 10, 15}, {5, 0, 20, 30}, {10, 20, 0, 35}, {15, 30, 35, 0}};
    V = dist.size();
    std::vector<std::vector<uint32_t>> dp1(1 << V, std::vector<uint32_t>(V, -1));
    assert(bit_manipulation::travelling_salesman_using_bit_manipulation::travelling_salesman_using_bit_manipulation(dist, 1, 0, V, dp1) == 75);
    std::cout << "Testcase 2 Passed" << "\n";
    //TestCase 3
    dist = {

Review comment (suggestion):
```suggestion
}  // namespace travelling_salesman_using_bit_manipulation
}  // namespace bit_manipulation
```


Code after:
        std::uint64_t n, // n is the no of cities we have.
        std::vector<std::vector<uint32_t>> &dp) //dp is taken to memorize the state to avoid recomputition
{
    //base case;
    if (setOfCities == (1 << n) - 1) // we have covered all the cities
        return dist[city][0]; //return the cost from the current city to the original city.

    if (dp[setOfCities][city] != -1)
        return dp[setOfCities][city];
    //otherwise try all possible options
    uint64_t ans = 2147483647 ;
    for (int choice = 0; choice < n; choice++) {
        //check if the city is visited or not.
        if ((setOfCities & (1 << choice)) == 0 ) { // this means that this perticular city is not visited.
            std::uint64_t subProb = dist[city][choice] + travelling_salesman_using_bit_manipulation(dist, setOfCities | (1 << choice), choice, n, dp);
            // Here we are doing a recursive call to tsp with the updated set of city/node
            // and choice which tells that where we are currently.
            ans = std::min(ans, subProb);
        }

    }
    dp[setOfCities][city] = ans;
    return ans;
}
} // namespace travelling_salesman_using_bit_manipulation
} // namespace bit_manipulation

/**
 * @brief Self-test implementations
 * @returns void
 */
static void test() {
    // 1st test-case
    std::vector<std::vector<uint32_t>> dist = {
        {0, 20, 42, 35}, {20, 0, 30, 34}, {42, 30, 0, 12}, {35, 34, 12, 0}
    };
    uint32_t V = dist.size();
    std::vector<std::vector<uint32_t>> dp(1 << V, std::vector<uint32_t>(V, -1));
    assert(bit_manipulation::travelling_salesman_using_bit_manipulation::travelling_salesman_using_bit_manipulation(dist, 1, 0, V, dp) == 97);
    std::cout << "1st test-case: passed!" << "\n";

    // 2nd test-case
    dist = {{0, 5, 10, 15}, {5, 0, 20, 30}, {10, 20, 0, 35}, {15, 30, 35, 0}};
    V = dist.size();
    std::vector<std::vector<uint32_t>> dp1(1 << V, std::vector<uint32_t>(V, -1));
    assert(bit_manipulation::travelling_salesman_using_bit_manipulation::travelling_salesman_using_bit_manipulation(dist, 1, 0, V, dp1) == 75);
    std::cout << "2nd test-case: passed!" << "\n";
    // 3rd test-case
    dist = {
        {0, 10, 15, 20}, {10, 0, 35, 25}, {15, 35, 0, 30}, {20, 25, 30, 0}
    };