Loading...
Loading...
Loading...
Arjun is making a playlist for a long train journey home. He has n different songs and wants to see every order in which they could play, with each song played exactly once.
Print all the orders, one per line, with the song names separated by spaces. List them in dictionary order: compare the first songs, then the second songs, and so on.
Example 1
Input
3 raga beat lofi
Output
beat lofi raga beat raga lofi lofi beat raga lofi raga beat raga beat lofi raga lofi beat
Sorted, the songs are beat, lofi, raga. Three songs give 3! = 6 orders.
Example 2
Input
1 melody
Output
melody
One song can play in only one order.
Try the problem first. Open one hint at a time.
Build an order one position at a time. At each position, try every song that is not used yet.
Keep a boolean[] used array so you can check in O(1) whether a song is already in the order.
Sort the names first. If you try songs in sorted order at every position, the orders come out in dictionary order.
After the recursive call returns, mark the song as unused and remove it, so the next song can take that position.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor