Every Running Order
EasyBacktrackingFree
Problem
A band has a set of songs, each identified by a distinct integer in nums. Return every possible running order: every arrangement that plays each song exactly once.
Return the orders in any sequence; the songs inside one order must, of course, be in that order's sequence.
Example 1
- Input:
- nums = [1, 2, 3]
- Output:
- [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
3 choices for the first slot, 2 for the second, 1 for the last: 3! = 6 orders.
Example 2
- Input:
- nums = [0, 1]
- Output:
- [[0, 1], [1, 0]]
Constraints
- 1 ≤ nums.length ≤ 7
- -10 ≤ nums[i] ≤ 10
- All values in nums are distinct.
Hint
Show the first hint
Fill the running order one slot at a time.
Walkthrough
How to approach it
01Clarify before coding
- Are all songs distinct? Yes, so no two generated orders can be equal.
- Does the order of the returned list matter? No, but each inner order is meaningful.
- How large can n get? At most 7, so 7! = 5040 orders: the output size dominates everything.
02Brute force
Generate all n^n sequences of indices and keep those that use every index exactly once.
Cost: O(n^n · n): for n = 7 that is 823,543 candidates for only 5,040 valid orders, nearly all wasted.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.