Leetcode: Permutation

Given a collection of numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

Understand the problem:
The problem gives a collection of numbers, ask for returning all possible permutations. 
For an array with length n, the number of possible permutations n! 

Recursive Solution:
It is not hard to think of a recursive solution. 

Code (Java):

public class Solution {
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        
        permute(num, 0, result);
        
        return result;
    }
    
    private void permute(int[] num, int start, ArrayList<ArrayList<Integer>> result) {
        if (start >= num.length) {
            ArrayList<Integer> temp = toArrayList(num);
            result.add(temp);
        }
        
        for (int i = start; i < num.length; i++) {
            swap(num, start, i);
            permute(num, start + 1, result);
            swap(num, start, i);
        }
    }
    
    private void swap(int[] num, int i, int j) {
        int temp = num[i];
        num[i] = num[j];
        num[j] = temp;
    }
    
    private ArrayList<Integer> toArrayList(int[] num) {
        int len = num.length;
        ArrayList<Integer> temp = new ArrayList<Integer>(len);
        for (int i = 0; i < len; i++) {
            temp.add(num[i]);
        }
        return temp;
    }
}

Summary:
The crux of this problem is using recursion. This problem is very similar to the palindrome partition. The only trick is to swap the number and swap them back. 

Update on 5/7/19:

public class Solution {
    /*
     * @param nums: A list of integers.
     * @return: A list of permutations.
     */
    public List<List<Integer>> permute(int[] nums) {
        // write your code here
        List<List<Integer>> ans = new ArrayList<>();
        boolean[] visited = new boolean[nums.length];
        
        permuteHelper(nums, visited, new ArrayList<Integer>(), ans);
        
        return ans;
    }
    
    private void permuteHelper(int[] nums, boolean[] visited, List<Integer> curList, List<List<Integer>> ans) {
        if (curList.size() == nums.length) {
            ans.add(new ArrayList<>(curList));
            return;
        }
        
        for (int i = 0; i < nums.length; i++) {
            if (visited[i]) {
                continue;
            }
            
            visited[i] = true;
            curList.add(nums[i]);
            permuteHelper(nums, visited, curList, ans);
            visited[i] = false;
            curList.remove(curList.size() - 1);
        }
    }
}