LeetCode笔记：46. Permutations

Cloudox

发布于 2021-11-23 14:00:43

1430

发布于 2021-11-23 14:00:43

问题：

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] ]

大意：

给出一个不同数字的集合，返回所有可能的排列。比如： [1,2,3] 有下面这些排列： [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

思路：

这就是中学时排列组合的题目，要极尽所有排列，我们就要从第一个位置开始所有的元素都有可能放一遍，第二个位置在放了第一个位置的数字后剩下的数字又都可能放一遍，第三个位置也是类似，一直到最后一个位置。

对于这种操作用递归最合适，在我们创建的函数中对于第i个位置，每个当前还剩下的数字都去尝试放一次，并且继续往下递归，最后就会得到所有可能的排列。

要注意的一点就是在递归中我们的List和数组都要进行深拷贝然后添加元素，否则不同的放置方式操作的都是同一个List或者数组，没有意义。

代码（Java）：

public class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> resList = new ArrayList<List<Integer>>();
        for (int i = 0; i < nums.length; i++) {
            List<Integer> list = new ArrayList<Integer>();
            list.add(nums[i]);
            int[] hasUsed = new int[nums.length];
            hasUsed[i] = 1;
            doPermute(nums, resList, list, hasUsed);
        }
        return resList;
    }
    
    public void doPermute(int[] nums, List<List<Integer>> resList, List<Integer> list, int[] hasUsed) {
        if (list.size() == nums.length) {
            resList.add(list);
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (hasUsed[i] == 0) {
                List<Integer> newList = new ArrayList<Integer>();
                newList.addAll(list);
                newList.add(nums[i]);
                int[] newUsed = hasUsed.clone();
                newUsed[i] = 1;
                doPermute(nums, resList, newList, newUsed);
            }
        }
    }
}

合集：https://github.com/Cloudox/LeetCode-Record

查看作者首页

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2017/11/27 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法