力扣第 46 题全排列简洁高效版

作者：极客罗杰

2024-10-19
上海
本文字数：537 字
阅读完需：约 2 分钟

题目：Permutations

Given a collection of distinct integers, return all possible permutations.

Example:

Input: [1,2,3]

Output:

[

[1,2,3],

[1,3,2],

[2,1,3],

[2,3,1],

[3,1,2],

[3,2,1]

]

关键点：使用 Set 来去重，减少函数调用

public List<List<Integer>> permute(int[] nums) {        List<List<Integer>> ret = new ArrayList<>();
        backtrack(ret, new ArrayList<>(), new HashSet<>(), nums);
        return ret;
    }
    private void backtrack(List<List<Integer>> ret, List<Integer> tmpList, Set<Integer> tmpSet, int[] nums) {        if (tmpSet.size() == nums.length) {            ret.add(new ArrayList<>(new ArrayList<>(tmpList)));            return;        }
        for (int i = 0; i < nums.length; i++) {            if (tmpSet.contains(nums[i])) continue;
            tmpSet.add(nums[i]);            tmpList.add(nums[i]);
            backtrack(ret, tmpList, tmpSet, nums);
            tmpSet.remove(tmpList.get(tmpList.size()-1));            tmpList.remove(tmpList.size()-1);        }    }