Recursion and Backtracking Generating every choice
319. Permutations
You are given an array nums of different integers. Return every arrangement of its values.
An arrangement is a list that holds every value of nums exactly once, in some order. Two arrangements
are different when some position holds different values in them, so [1,2] and [2,1] are two
arrangements. nums itself is one of the arrangements.
The arrangements can come back in any order. The order of the values inside each arrangement is what makes it that arrangement, so that order matters. The examples sort the arrangements by their first value, then by their second value, and so on.
Example 1
Input: nums = [7, -2, 4]
[[-2,4,7],
[-2,7,4],
[4,-2,7],
[4,7,-2],
[7,-2,4],
[7,4,-2]]Explanation: Any of the three values can come first, and the other two then go in either order. That gives
3 × 2 = 6 arrangements, and [7,-2,4] itself is one of them.
Example 2
Input: nums = [5]
[[5]]Explanation: One value has exactly one arrangement, the array itself.
Example 3
Input: nums = [1000000000, -1000000000]
[[-1000000000,1000000000],[1000000000,-1000000000]]Explanation: Two values give two arrangements, the array and its reverse. The values can be as large or as small as 109 and −109.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ nums.length ≤ 7-109 ≤ nums[i] ≤ 109- All the values in
numsare different.
Clarifying questions
What you would ask an interviewer before writing any code.