The problem is great and its a standard Travelling Salesman Problem, which can be solved using Dynamic Programming or by generating all the permutations of the cities.
I had submitted and got my solution accepted with both the methods, but neither of those gets all the preliminary “Test” cases passed, whereas all the “Submit” button test cases work fine for my solution.
After a while of debugging and going through the editorial solution after my problem got submitted, I noticed the editorial solution does it by generating all the permutations (not an optimized way) and further checks if a particular path from city i to city j is not zero, only then it uses city i and j in the path [The assumption in the editorial is any city path if zero, it should mean its a self path and should be ignored]. This clearly fails for the test case-
A : 4 B : [ [0, 1, 2, 3] [3, 0, 2, 1] [5, 6, 0, 7] [8, 9, 0, 0] ] Your function returned the following : 7 The expected returned value : 17 -- You can test this by entering the custom case: 4 4 4 0 1 2 3 3 0 2 1 5 6 0 7 8 9 0 0
Note here, the path should be
0->1->3->2->0 :: Sum here should be
1 + 1 + 0 + 5 = 7
But the editorial does not include this path in the answer gives the next minimum cost of travelling which is 17. Clearly its not the right answer.
I hope InterviewBit team fixes this soon. The editorial solution can be fixed with just removing the zero check inside the void tsp(…) function.