Create a recursive, decrease-and-conquer function PERMUTATIONS that receives an array nums of distinct integers and returns all permutations of nums such that all permutations ending in an even number come before all permutations ending in an odd number. Your code must pass all test cases at https://leet code.com/problems/permutations/. Note: the given problem on Leet Code requires the permutations in any order. You must output the permutations in the order described above to receive full credit. Note also that there are some solutions posted on Leet Code that do not use decrease and conquer or recursion and do not output the permutations in the required order. These are not acceptable solutions. Some solutions posted may also be incorrect. In any case, if we find a solution that is largely copied from another source (e.g., verbatim or simply with different variable names), it will be considered a violation of the academic honesty policy. Example 1 input: [1, 4, 5] output: [[1, 5, 4], [5, 1, 4], [1, 4, 5], [4, 1, 5], [4, 5, 1], [5, 4, 1]] Example 2 input: [1, 2] output: [[1, 2], [2, 1]] Example 3 input: [1, 3, 5, 7] output: [[1, 3, 5, 7], [1, 3, 7, 5], [1, 5, 3, 7], [1, 5, 7, 3], [1, 7, 3, 5], [1, 7, 5, 3], [3, 1, 5, 7], [3, 1, 7, 5], [3, 5, 1, 7], [3, 5, 7, 1], [3, 7, 1, 5], [3, 7, 5, 1], [5, 1, 3, 7], [5, 1, 7, 3], [5, 3, 1, 7], [5, 3, 7, 1], [5, 7, 1, 3], [5, 7, 3, 1], [7, 1, 3, 5], [7, 1, 5, 3], [7, 3, 1, 5], [7, 3, 5, 1], [7, 5, 1, 3], [7, 5, 3, 1]]