permutations.md

46. Permutations - 全排列

Tags - 题目标签

Description - 题目描述

EN:

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

 

Example 1:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2:

Input: nums = [0,1]
Output: [[0,1],[1,0]]

Example 3:

Input: nums = [1]
Output: [[1]]

 

Constraints:

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• All the integers of nums are unique.

ZH-CN:

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

 

示例 1：

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

示例 2：

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

示例 3：

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

 

提示：

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

Link - 题目链接

LeetCode - LeetCode-CN

Latest Accepted Submissions - 最近一次 AC 的提交

Language	Runtime	Memory	Submission Time
typescript	76 ms	47.1 MB	2022/05/08 23:47

function permute(nums: number[]): number[][] {

  if (nums.length === 1) {
    return [nums];
  }

  let res: number[][] = [];

  function dfs(idx: number): void {
    if (idx === nums.length) {
      return;
    }

    if (idx === 1) {
      res = [[nums[0], nums[1]], [nums[1], nums[0]]];
      dfs(idx+1);
      return;
    }

    res = res.reduce((acc: number[][], item) => {
      const newItem: number[][] = [];
      for (let i = 0; i <= item.length; i++) {
        newItem.push([
          ...item.slice(0, i),
          nums[idx],
          ...item.slice(i),
        ])
      }
      return [...acc, ...newItem];
    }, [])


    dfs(idx+1);
  }

  dfs(1);

  return res;

};

My Notes - 我的笔记

No notes