C++ question

Problem 1 Permutations Given an array nums of distinct integers, return all the possible permutations. You must return the permutations in an order such that any permutation can be obtained from the previous permutation by swapping a single pair of elements. Example 1 Input: nums = [1,2,3] Output: [1,2,3], [2,1,3), (2,3,1],[1,3,2), (3, 1, 2), (3, 2, 1] Note that each permutation in the above ordering can be obtained by swapping exactly one pair of elements from the previous permutation. Example 2 Input: nums = [0, 1] Output: [0,1],[1,0) Example 3 Input: nums = [1] Output: Output: [1] It is important that you solve this problem using recursion. That is, you have to reduce the original problem into one or more subproblem, recursively solve the subproblems, and then combine the solutions to obtain the solution to the original problem. Your solution should take O(n!) time. A solution that does not use recursion will receive a zero. Note that the Leet Code webpage allows the permutations to be output in any order. By contrast, we require the permutations to be output such that any two consecutive permutations differ by swapping a single pair of elements. Additionally, some solutions on Leet Code do not use recursion. These are not acceptable solutions. Some solutions posted may also be wrong. In any case, a solution that is largely copied from another source (e.g., verbatim or made to look different by simply changing variable names) will be in violation of the Academic Honesty Policy. The following must be submitted. (a) Writeup (50 Points) Pseudocode for your solution, with an explanation in words why your solution works. (25 points) Analysis, showing the correctness of your algorithm and its complexity (i.e., its runtime). (25 points)