当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.046.Permutations 全排列

LeetCode.046.Permutations 全排列

题目描述

46 Permutations
https://leetcode-cn.com/problems/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]
]

解题过程

全排列问题是一个非常经典的 回溯法 backtracking 应用,全排列的代码可以直接作为回溯法的代码模板,非常值得一做的题目。
n 个数的全排列有 n!
对于第一个位置,可选的数有 n 个,第一个位置选择完毕后,第二个位置有 n-1 个选择,以此类推。
假如第一个位置选择 nums[0] ,并把所有其他位置选择完毕后,我们需要回退撤销第一个选择 nums[0] ,继续选择 nums[1] 放在第一个位置。

需要注意的地方:
1、满足结束条件 或 到达解空间叶子节点后,把当前选择加入结果集 resultSet 时,需要做一次拷贝,否则由于 Java 中的引用传递的是地址,后续操作会继续修改已经完成的选择,当然如果使用 String 则没有这个问题,使用其他集合类存储选择结果时都需要注意。
2、用 stack 存储当前选择,方便在末尾 push(选择) 和 pop(撤销), LinkedList 实现了 Deque 接口,可当做栈使用。
3、我这里使用 Set 存储剩余可用选择,是一种很低效的浪费空间的做法,但方便理解,可以参考官方解法中的直接在原数组上用下标分隔已选和未选元素,并使用 Collections.swap 进行选择和撤销,或者,使用一个 boolean[] selected 数组标记是否选择过。

可以参考 liweiwei 这个全排列的题解,以全排列问题为切入点,全面介绍了回溯法,很详细
从全排列问题开始理解「回溯」算法(深度优先遍历 + 状态重置 + 剪枝)
https://leetcode-cn.com/problems/permutations/solution/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liweiw/

时间复杂度 O(n*n!),空间复杂度O(n*n!)

private static class SolutionV2020 {
    private List<List<Integer>> res;
    public List<List<Integer>> permute(int[] nums) {
        if (null == nums || 0 == nums.length) {
            return Collections.emptyList();
        }
        res = new ArrayList<>();
        Set<Integer> choices = Arrays.stream(nums).boxed().collect(Collectors.toSet());
        backtrace(new LinkedList<>(), choices);
        return res;
    }

    /**
     * 回溯
     * @param permute 当前的排列,用 stack 存储方便在末尾 push(选择) 和 pop(撤销), LinkedList 实现了 Deque 接口,可当做栈使用
     * @param choices 当前可用的选择 集合
     */
    private void backtrace(LinkedList<Integer> permute, Set<Integer> choices) {
        if (choices.size() == 0) {
            // 剩余可用选择为0,结束,加入结果集
            res.add(new ArrayList<>(permute));
            return;
        }
        // 遍历选择列表
        for (Integer choice : new HashSet<>(choices)) {
            permute.push(choice); // 选择 choice 加入排列
            choices.remove(choice); // 把 choice 从剩余可用选择集合中删除
            backtrace(permute, choices); // 递归进行后续选择
            permute.pop(); // 回退撤销 choice 选择
            choices.add(choice); // 把 choice 恢复到剩余可用选择集合
        }
    }
}

GitHub代码

algorithms/leetcode/leetcode/_046_Permutations.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_046_Permutations.java


上一篇 LeetCode.023.Merge k Sorted Lists 合并K个排序链表

下一篇 LeetCode.剑指offer.051.数组中的逆序对

阅读
评论
749
阅读预计3分钟
创建日期 2020-04-25
修改日期 2020-04-25
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论