Write a program that asks the user to input a number n and prints all permutations of the sequence of numbers 1, 2, 3, ..., n.

For example, if n is 3, the program should print1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 Hint: Write a function permutation_helper(vector prefix, vector to_permute)that computes all the permutations in the array to_permute and prints each permutation,prefixed by all numbers in the array prefix.

For example, if prefix contains the number 2 and to_permute the numbers 1 and 3, then permutation_helper prints2 1 3 2 3 1 The permutation_helper function does the following: If to_permute has no elements, print the elements in prefix. Otherwise, for each element e in to_permute, make an array to_permute2 that is equal to permute except for e and an array prefix2 consisting of prefix and e. Then call permutation_helper with prefix2 and to_permute2