Permutations

Medium

Given an array `nums` of distinct integers, return all the possible permutations. You can return the answer in any order.

Example 1:

```Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
```

Example 2:

```Input: nums = [0,1]
Output: [[0,1],[1,0]]
```

Example 3:

```Input: nums = [1]
Output: [[1]]```

Constraints:

• `1 <= nums.length <= 6`
• `-10 <= nums[i] <= 10`
• All the integers of `nums` are unique.

Backtracking is an algorithm for finding all solutions by exploring all potential candidates. If the solution candidate turns to be not a solution (or at least not the last one), backtracking algorithm discards it by making some changes on the previous step, i.e. backtracks and then try again.

Here is a backtrack function which takes a `currentList` which have the current combination and a `resultList` which contains the all possible permutations.

• If the currentList size is equal to the input array length then we are done with one such permutation.
• Iterate over the integers from `0th` index to index `n - 1`.
• Place `i-th` integer in the permutation, and mark this as `used`.
• Proceed to create all permutations and add digits in the permutation which are not used in the previous call.
• Now backtrack, i.e. mark the previously used digits as unused and remove the same from the currentList.
```class Solution {
public List<List<Integer>> permute(int[] nums) {

List<List<Integer>> result = new ArrayList<>();
if (nums == null || nums.length == 0) {
return result;
}
List<Integer> current = new ArrayList<>();
boolean[] used = new boolean[nums.length];
generatePermutations(nums, current, used, result, nums.length);
return result;
}

private void generatePermutations(int[] nums, List<Integer> current,
boolean[] used, List<List<Integer>> result, int n) {
if (n == current.size()) {
} else {
for (int i = 0; i < n; i++) {
int cur = nums[i];
if (used[i]) continue;