1107. Hamiltonian Path Existence (Bitmask DP)

Given an undirected graph with n nodes and edges, determine whether a Hamiltonian path exists — a path visiting every node exactly once. Return true or false. The input is JSON {n, edges}.

Input: JSON {n, edges}.

Output: Boolean — true or false.

Examples

Input: {"n":4,"edges":[[0,1],[1,2],[2,3]]}
Output: true
Explanation: The chain is a Hamiltonian path.

Input: {"n":4,"edges":[[0,1],[0,2],[0,3]]}
Output: false
Explanation: A star has no Hamiltonian path.

Input: {"n":1,"edges":[]}
Output: true
Explanation: A single node trivially qualifies.

Constraints

• 1<=n<=16

Asked by