1. import java.util.*;
2.  
3. public class TravelingSalesmanHeldKarp {
4.  
5.     private static int INFINITY = 100000000;
6.  
7.     private static class Index {
8.         int currentVertex;
9.         Set<Integer> vertexSet;
10.  
11.         @Override
12.         public boolean equals(Object o) {
13.             if (this == o) return true;
14.             if (o == null || getClass() != o.getClass()) return false;
15.  
16.             Index index = (Index) o;
17.  
18.             if (currentVertex != index.currentVertex) return false;
19.             return !(vertexSet != null ? !vertexSet.equals(index.vertexSet) : index.vertexSet != null);
20.         }
21.  
22.         @Override
23.         public int hashCode() {
24.             int result = currentVertex;
25.             result = 31 * result + (vertexSet != null ? vertexSet.hashCode() : 0);
26.             return result;
27.         }
28.  
29.         private static Index createIndex(int vertex, Set<Integer> vertexSet) {
30.             Index i = new Index();
31.             i.currentVertex = vertex;
32.             i.vertexSet = vertexSet;
33.             return i;
34.         }
35.     }
36.  
37.     private static class SetSizeComparator implements Comparator<Set<Integer>>{
38.         @Override
39.         public int compare(Set<Integer> o1, Set<Integer> o2) {
40.             return o1.size() - o2.size();
41.         }
42.     }
43.  
44.     public int minCost(int[][] distance) {
45.  
46.         //stores intermediate values in map
47.         Map<Index, Integer> minCostDP = new HashMap<>();
48.         Map<Index, Integer> parent = new HashMap<>();
49.  
50.         List<Set<Integer>> allSets = generateCombination(distance.length - 1);
51.  
52.         for(Set<Integer> set : allSets) {
53.             for(int currentVertex = 1; currentVertex < distance.length; currentVertex++) {
54.                 if(set.contains(currentVertex)) {
55.                     continue;
56.                 }
57.                 Index index = Index.createIndex(currentVertex, set);
58.                 int minCost = INFINITY;
59.                 int minPrevVertex = 0;
60.                 //to avoid ConcurrentModificationException copy set into another set while iterating
61.                 Set<Integer> copySet = new HashSet<>(set);
62.                 for(int prevVertex : set) {
63.                     int cost = distance[prevVertex][currentVertex] + getCost(copySet, prevVertex, minCostDP);
64.                     if(cost < minCost) {
65.                         minCost = cost;
66.                         minPrevVertex = prevVertex;
67.                     }
68.                 }
69.                 //this happens for empty subset
70.                 if(set.size() == 0) {
71.                     minCost = distance[0][currentVertex];
72.                 }
73.                 minCostDP.put(index, minCost);
74.                 parent.put(index, minPrevVertex);
75.             }
76.         }
77.  
78.         Set<Integer> set = new HashSet<>();
79.         for(int i=1; i < distance.length; i++) {
80.             set.add(i);
81.         }
82.         int min = Integer.MAX_VALUE;
83.         int prevVertex = -1;
84.         //to avoid ConcurrentModificationException copy set into another set while iterating
85.         Set<Integer> copySet = new HashSet<>(set);
86.         for(int k : set) {
87.             int cost = distance[k][0] + getCost(copySet, k, minCostDP);
88.             if(cost < min) {
89.                 min = cost;
90.                 prevVertex = k;
91.             }
92.         }
93.  
94.         parent.put(Index.createIndex(0, set), prevVertex);
95.         printTour(parent, distance.length);
96.         return min;
97.     }
98.  
99.     private void printTour(Map<Index, Integer> parent, int totalVertices) {
100.         Set<Integer> set = new HashSet<>();
101.         for(int i=0; i < totalVertices; i++) {
102.             set.add(i);
103.         }
104.         Integer start = 0;
105.         Deque<Integer> stack = new LinkedList<>();
106.         while(true) {
107.             stack.push(start);
108.             set.remove(start);
109.             start = parent.get(Index.createIndex(start, set));
110.             if(start == null) {
111.                 break;
112.             }
113.         }
114.         StringJoiner joiner = new StringJoiner("->");
115.         stack.forEach(v -> joiner.add(String.valueOf(v)));
116.         System.out.println("\nTSP tour");
117.         System.out.println(joiner.toString());
118.     }
119.  
120.     private int getCost(Set<Integer> set, int prevVertex, Map<Index, Integer> minCostDP) {
121.         set.remove(prevVertex);
122.         Index index = Index.createIndex(prevVertex, set);
123.         int cost = minCostDP.get(index);
124.         set.add(prevVertex);
125.         return cost;
126.     }
127.  
128.     private List<Set<Integer>> generateCombination(int n) {
129.         int input[] = new int[n];
130.         for(int i = 0; i < input.length; i++) {
131.             input[i] = i+1;
132.         }
133.         List<Set<Integer>> allSets = new ArrayList<>();
134.         int result[] = new int[input.length];
135.         generateCombination(input, 0, 0, allSets, result);
136.         Collections.sort(allSets, new SetSizeComparator());
137.         return allSets;
138.     }
139.  
140.     private void generateCombination(int input[], int start, int pos, List<Set<Integer>> allSets, int result[]) {
141.         if(pos == input.length) {
142.             return;
143.         }
144.         Set<Integer> set = createSet(result, pos);
145.         allSets.add(set);
146.         for(int i=start; i < input.length; i++) {
147.             result[pos] = input[i];
148.             generateCombination(input, i+1, pos+1, allSets, result);
149.         }
150.     }
151.  
152.     private static Set<Integer> createSet(int input[], int pos) {
153.         if(pos == 0) {
154.             return new HashSet<>();
155.         }
156.         Set<Integer> set = new HashSet<>();
157.         for(int i = 0; i < pos; i++) {
158.             set.add(input[i]);
159.         }
160.         return set;
161.     }
162. }