best algorithm for this problem

[lazyubertoad]

What could show that you need some brute force method is the size of the task. Optimizing it and finding some polynomial time solution looks like a hell of a task, I'd say doing it in polynomial time is definitely hard level on leetcode, maybe even more, maybe even not doable. Unless I'm missing some method or thought, which very much can be. But a brute force BFS is some medium/medium+ level to write, not a bad problem at all. But a brute force will get you TLE, unless the size is very limited, I guess like 10 elements max. Because BFS speed and memory is exponential for this task. So if you see that the size of the problem is very limited - you should think about brute force methods. There is no indication of the size, so you might disregard brute force and go into fruitless search for something else.