46. Permutations

Permutations

Given a collection of distinct 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], [3,2,1] ]

Solution

public class Solution {
    public List<List<Integer>> permute(int[] nums) {

  List<List<Integer>> result = new ArrayList<List<Integer>>();
        permutae(result, nums, 0, new ArrayList<Integer>());
        return result;
    }

    public void permutae(List<List<Integer>> result, int[] nums, int index, List<Integer> current) {
        if (index == nums.length) {
            result.add(current);
            return;
        }

        int currentValue = nums[index];
        for(int i = 0; i <= current.size(); i ++) {
            List<Integer> newList = new ArrayList<Integer>(current);
            newList.add(i, currentValue);
            permutae(result, nums, index + 1, newList);
        }
    }
}