Traveling Salesman Problem

Problem Statement

You are given a set of n cities and a distance matrix dist[][], where dist[i][j] represents the cost to travel from city i to city j.

Your task is to:

• Start from city 0.
• Visit every city exactly once.
• Return back to city 0.
• And find the minimum total travel cost.

Examples

Example 1:
 
Input:
 N = 4
       dist = [
               [0, 10, 15, 20],
               [10, 0, 35, 25],
               [15, 35, 0, 30],
               [20, 25, 30, 0]
              ]

Output:
 80

Explanation: One of the optimal paths: 0 → 1 → 3 → 2 → 0
Cost = 10 + 25 + 30 + 15 = 80

Different Approaches

1️⃣ Brute Force Approach (Generate All Permutations)