Description

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

DFS

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> permutations = new ArrayList<>();
        if (nums == null || nums.length < 1) return permutations;

        List<Integer> permutation = new ArrayList<>();
        permuteRecur(nums, 0, permutation, permutations);
        return permutations;
    }

    public void permuteRecur(int[] nums
            , int begin
            , List<Integer> permutation
            , List<List<Integer>> permutations) {
        if (begin >= nums.length) {
            permutations.add(new ArrayList<>(permutation));
            return;
        }

        for (int i = begin; i < nums.length; ++i) {
            swap(nums, begin, i);
            permutation.add(nums[begin]);   // not nums[i]!
            permuteRecur(nums, begin + 1, permutation, permutations);
            swap(nums, begin, i);
            permutation.remove(permutation.size() -1);
        }
    }

    public void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}