String permutations are the various possible strings made by the **rearrangement** of the characters in the original String.

For example, the permutations of `car`

are

car, cra, acr, arc, rac, rca

Write a **recursive** method `getPermutations()`

that returns all permutations of an input `String`

in an `ArrayList`

.
Define a helper method if needed. For the sake of simplicity, assume that all characters in the input `String`

are unique.

Examples:

`getPermutations("") -> ArrayList -> []`

`getPermutations("c") -> ArrayList -> ["c"]`

`getPermutations("cat") -> ArrayList -> ["cat","cta","act","atc","tca","tac"]`

^{*}

Need a **hand?** Try out these hints, one at a time.

permutation(N) = N!

1. N! = N*(N-1)*(N-2)*(N-3) *.......3*2*1.

2. N-1! = (N-1)*(N-2)*(N-3) *.......3*2*1.

3. By 1 and 2, we can derive, N! = N * ((N-1)!)

Think how can this formula help you.

Separate out each of the characters from the input**remaining** String (you'll find the substring() method useful).The permutation of an empty String is an empty String. This could be the base condition.

1. N! = N*(N-1)*(N-2)*(N-3) *.......3*2*1.

2. N-1! = (N-1)*(N-2)*(N-3) *.......3*2*1.

3. By 1 and 2, we can derive, N! = N * ((N-1)!)

Think how can this formula help you.

Separate out each of the characters from the input

`String`

one by one and recurse to find the permutation of the To permute a set S, we can select the first character and permute the rest of the characters of the string to get a new list of all possible permutations. Now “push” the first character into each possible position.

For example, if our string is “`abc`

”, we would do the following:

1. Let `first = “a”`

and let `remainder = “bc”`

.

2. Let `list = permute(bc) = {“bc”, “cd”}`

.

3. Push “`a`

” into each location of `“bc” (--> “abc”, “bac”, “bca”) `

and `“cb” (--> “acb”, “cab”, “cba”) `

.

4. Return this new Arraylist.

public static ArrayList<String> getPermutations(String s) { }

**C**

**Java**

**Python**