46. Permutations

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;
    }
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容