Posted on by seeker

LeetCode – 46 : Permutations

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]
]
[code lang="java"]
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        
    }
}
[code]

Idea – 1

With n distinct numbers, there are n! distinct permutations. We shall do dfs, first level has n choices, second level has n-1 choices, so on. Any solution has time complexity O(n\cdot n!). Output has size O(n\cdot n!). Additional space complexity is O(n). 
[code lang="java"]
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if(nums==null || nums.length==0)
        {
            return result;
        }
        
        boolean[] visited = new boolean[nums.length];
        
        collect(nums, visited, new LinkedList<Integer>(), result);
        
        return result;
    }
    
    private void collect(int[] nums, boolean[] visited, LinkedList<Integer> buffer, List<List<Integer>> result)
    {
        if(buffer.size() == nums.length)
        {
            result.add(new ArrayList<>(buffer));
            return;
        }
        
        for(int i = 0; i < visited.length; ++i)
        {
            if(!visited[i])
            {
                visited[i] = true;
                buffer.addLast(nums[i]);
                collect(nums, visited, buffer, result);
                buffer.removeLast();
                visited[i] = false;
            }
        }
    }
}
[code]

Runtime: 1 ms, faster than 99.75% of Java online submissions for Permutations.Memory Usage: 36.6 MB, less than 96.01% of Java online submissions for Permutations.