LeetCode_89_Permutations

LeetCode

发布日期: 2022-06-08

更新日期: 2022-06-08

文章字数: 811

阅读时长: 3 分

阅读次数:

1. question: 全排列（中等）

给定一个不含重复数字的数组 nums ，返回其所有可能的全排列。你可以按任意顺序返回答案。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/permutations

示例 1：

1 2	输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

1 2	输入：nums = [0,1] 输出：[[0,1],[1,0]]

示例 3：

1 2	输入：nums = [1] 输出：[[1]]

提示：

1
2
3

1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同

2. answers

这道题是排列问题，即组合的元素是有序的。相对于前面的子集组合等问题，有如下区别：

组合的长度和给定的数组是相同的；
不同的组合，只要有一个对应下标位置的元素不同，那么组合就不算重复。

简单地说，就是每个元素都可以取数组中的全部值。但是必须要和前面的元素取值不同。以[1,2,3]为例，第一个元素有三种选择，如果它选了1，那么第二个元素只能选2或者3，如果它选了2，第三个元素只能选3。反过来，如果第一个元素元素选了2，那么第二个元素能选1或者3，如果选了1，第三个元素只能选3。

总之，一个组合中，每个元素都可以取数组中的全部值，并且只能是在前面元素挑剩下的数组元素中选择。因此，总体步骤和组合类似，只不过在递归下一个元素的时候，需要传入下一个元素所能选取的元素。递归终止条件是组合的长度为数组的长度。

为了传入下一个元素所选取的元素，设置一个辅助空间，保存应该下一个元素应该选取的集合，为了方便，我存储的是下标。代码如下所示：

public class Solution_0088 {

    public List<List<Integer>> result = new ArrayList<>();

    public LinkedList<Integer> group = new LinkedList<>();

    public void generatePmt(int[] nums, ArrayList<Integer> lList) {

        if(group.size() == nums.length) {

            result.add(new ArrayList<>(group));
            return;
        }

        for (int i = 0; i < lList.size(); i++) {

            group.add(nums[lList.get(i)]);

            // 递归下一个元素，注意，传入的lList
            // 每次都相对于本元素，是除掉本元素的取值，注意值传递和引用传递。这里新开辟的空间，必须是值传递，否则第一层的递归会影响
            // 本元素的后续选择。
            ArrayList<Integer> temp = new ArrayList<>(lList);
            temp.remove(i);
            generatePmt(nums, temp);

            // 回溯
            group.removeLast();
        }

    }

    public List<List<Integer>> permute(int[] nums) {

        ArrayList<Integer> indexArr = new ArrayList<>();

        for (int i = 0; i < nums.length; i++) {
            indexArr.add(i);
        }

        generatePmt(nums, indexArr);

        return result;
    }

    public static void main(String[] args) {
        System.out.println();

//        int[] nums = {1, 2, 3};
//        int[] nums = {0, 1};
        int[] nums = {1};

        Solution_0088 s = new Solution_0088();

        List<List<Integer>> result = s.permute(nums);

        for(List<Integer> list: result){

            for(Integer i: list)
                System.out.print(i + "\t");

            System.out.println();
        }
    }
}