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){
           result.add(new ArrayList<Integer>(temp));
           return;
       }
       for(int i=0;i<nums.length;i++){
           if(temp.contains(nums[i])) continue;
           temp.add(nums[i]);
           helper(nums, temp, result);
           temp.remove(temp.size()-1);
       }
   }
}