Plz give me the algorithm pseudocode and induction step proof.

2 Permutation in-place (50 pts) Design a recursive backtracking algorithm that outputs all possible permutations of an array of n elements in-place (i.e., your algorithm should not use more than O(1) additional space). Write down the pseudocode, and prove that your algorithm correctly prints out all permutations (Hint: use induction). No points will be given for an algorithm without the correctness proof. You may call the following procedures from within your algorithm: - Print(A,p,r) - to print the subarray A[p..r] - SWAP(A,i,j) - to exchange the items A[i] and A[j] within the array A