Permutations

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].

Java

public class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> rst = new ArrayList<List<Integer>>();
        helper(nums, new boolean[nums.length], new ArrayList<Integer>(), rst);
        return rst;
    }

    private void helper(int[] nums, boolean[] visited, List<Integer> item, List<List<Integer>> rst) {
        if(item.size() == nums.length) {
            rst.add(new ArrayList<Integer>(item));
            return;
        }

        for(int i = 0; i < nums.length; i++) {
            if(!visited[i]) {
                visited[i] = true;
                item.add(nums[i]);
                helper(nums, visited, item, rst);
                visited[i] = false;
                item.remove(item.size() - 1);
            }
        }
    }
}