Permutations

#1

Given a collection of distinct integers, return all possible permutations.

Example:

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

#2

The below code uses a queue to generate permutations of all numbers. Like if you start with a list `[1, 2, 3]`, we start with an empty list, `[[]`.

Add the first element from the input to this list, `[[1]]`, the for every other element, see how many places you can add the list. Like the list grows like this,

``````[[1]]
[[2, 1], [1, 2]]
[3, 2, 1], [2, 3, 1], [2, 1, 3]...etc

``````

Below is the Golang code that beats 100% OJ:

``````type Queue [][]int

func (q *Queue) Push(n []int) {
*q = append(*q, n)
}

func (q * Queue) Pop() (n []int) {
if q.Len()!=0{
n = (*q)[0]
*q = (*q)[1:]
return n
}

return []int{}
}

func (q * Queue) Len() int {
return len(*q)
}

func (q *Queue) Peek() []int{
if q.Len()!=0{
n := (*q)[0]
return n
}

return []int{}
}

func permute(nums []int) [][]int {
result := make([][]int, 0)
if len(nums)==0 {
return result
}
list := new(Queue)
for i:=0;i<len(nums);i++{
for len(list.Peek())==i{
t := list.Pop()
for j:=0;j<=i;j++{
jt := make([]int, 0)
jt = append(jt, t[0:j]...)
jt = append(jt, nums[i])
jt = append(jt, t[j:]...)
list.Push(jt)
}
}
}

for list.Len()!=0 {
result = append(result, list.Pop())
}

return result
}
``````

#3

The below code uses backtracking to put together all possible combinations.

``````class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
if(nums==null || nums.length==0) return result;
helper(nums, new ArrayList<Integer>(), result);
return result;
}

private void helper(int[] nums, List<Integer> temp, List<List<Integer>> result){
if(temp.size() == nums.length){