linye's Blog

全端工程師心得分享

0%

[LeetCode]46. Permutations

發表於 分類於 ，

Algorithm I 筆記撰寫計畫

敘述

這是 Algorithm I 的第十一天第二個題目，總共有三題。

給你一個數字陣列 nums ，回傳這個數字陣列的所有可能不重複排序。

點我開啟限制與範例

限制:

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

Example 1:

1
2
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:

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

Example 3:

1
2
Input: nums = [1]
Output: [[1]]
點我開啟思路

思路

用選擇樹 Backtracking 的方式去做答

  1. 選一個根元素
  2. 在剩下的元素裡選一個
  3. 重複步驟二直到選完
  4. 把現在選好的陣列放入答案陣列

終止條件: 全部選完

撤銷選擇

筆記

因為這題也是屬於 Backtracking 類型的題目，所以用跟 77. Combinations 一樣的方法來作即可。

程式

function permute(nums: number[]): number[][] {
  let permutations: number[][] = [];
  function _dfs(preGoPath: number[], visitedPath: number[] = []): void {
    // 退出條件
    if (visitedPath.length === nums.length) {
      permutations.push(visitedPath);
      return;
    }

    // 選父層的 node 然後把可選的選項 (path) 丟入子層
    for (let i = 0; i < preGoPath.length; i++) {
      // 把選到的 node 放進 visitedPath 中
      visitedPath.push(preGoPath[i]);

      // 把剩下的丟進遞迴， visitedPath 需要解構賦值，避免互相影響
      _dfs(preGoPath.slice(0, i).concat(preGoPath.slice(i + 1)), [...visitedPath]);

      // 重選父層 node
      visitedPath.shift();
    }
    return;
  }
  _dfs(nums);

  return permutations;
};

成績

score-image;