A simple solution as shown below.
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class PathFinder {
private static void printPath(List path) {
for (int i = 0; i < path.size(); i++) {
System.out.format("%2d", path.get(i));
if (i != path.size() - 1)
System.out.print("->");
else
System.out.println();
}
}
private boolean shouldSkip(List curPath, Integer pos) {
if (curPath == null)
return false;
for (Integer i : curPath) {
if (pos <= i) {
return true;
}
}
return false;
}
public void findPaths(Map> graph, int curPos,
List curPath, int expectedPathLen) {
curPath.add(curPos);
if (curPath.size() == expectedPathLen) {
printPath(curPath);
} else {
List children = graph.get(curPos);
if (children != null) {
for (Integer i : children) {
if (this.shouldSkip(curPath, i))
continue;
findPaths(graph, i, curPath, expectedPathLen);
}
}
}
curPath.remove(curPath.size() - 1);
}
public static void main(String[] args) {
Map> graph = new HashMapInteger>>();
// construct a graph
// 0 -> 1 -> 2 -> 3 ->4 ->5 ->6 ->7 ->8 -> 9 ->10 ->11
// 0 -> 2
// 1 -> 5
// 4 -> 6
// 7 -> 6 (a backward path)
for (int i = 0; i <= 10; i++) {
graph.put(i, new ArrayList());
graph.get(i).add(i + 1);
}
graph.get(0).add(2);
graph.get(1).add(5);
graph.get(4).add(6);
graph.get(7).add(6);
// a variable used to record current path
List curPath = new ArrayList();
new PathFinder().findPaths(graph, 0, curPath, 10);
// output
// 0-> 1-> 2-> 3-> 4-> 5-> 6-> 7-> 8-> 9
// 0-> 1-> 2-> 3-> 4-> 6-> 7-> 8-> 9->10
// 0-> 2-> 3-> 4-> 5-> 6-> 7-> 8-> 9->10
// 0-> 2-> 3-> 4-> 6-> 7-> 8-> 9->10->11
}
}