Question

题目内容

解题思路

回溯 + 剪枝。

• 每一位都有 3 种选择：1、2、3。
• 每一次都做选择，展开出一棵空间树。
• 利用 hashMap，记录选过的数，下次遇到相同的数，跳过。

代码实现

const permute = (nums: number[]): number[][] => {
  const res: number[][] = [];
  const used: Record<string, boolean> = {};
  const dfs = (path: number[]) => {
    if (path.length === nums.length) {
      res.push(path.slice());
      return;
    }
    for (const num of nums) {
      if (used[String(num)]) continue;
      path.push(num);
      used[String(num)] = true;
      dfs(path);
      path.pop();
      used[String(num)] = false;
    }
  };
  dfs([]);
  return res;
};