Dsa
Backtracking
Medium
Artifact Chain Assembler
You are given N fragments of an ancient artifact. Each fragment has a left connector value and a right connector value (integers). You need to find a sequence of exactly K distinct fragments such that each fragment's right connector matches the next fragment's left connector. Additionally, the sequence must form a loop: the right connector of the last fragment must match the left connector of the first fragment. Print the space-separated indices of the fragments (using their 0-indexed order in the input) that form the lexicographically smallest sequence of indices. If no such loop exists, print 'None'.
Example:
Input:
3 4
1 2
2 3
3 1
1 3
Output:
0 1 2
(Explanation: Fragment 0 (1,2), 1 (2,3), and 2 (3,1) form a chain 1-2-3-1 of length 3.)
Key concepts
backtrackingcyclespermutations
Practise this out loud — free
Start a mock interview on THIS exact question — a voice AI interviewer opens with it, pushes back like a real onsite, then hands you an instant scorecard.
🎙 Practise this question now