全排列&&旋转图像&&字母异位词分组

旋转图像和字母异位分词感觉实现难度不大，主要是一开始没想到要怎么解，全排列的回溯在想法和实现上都有一定难度，所以今天主要总结全排列。

题目详情

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

解题思路

回溯的主要思想还是使用 DFS 遍历全部组合，然后把合适的组合加入结果中，假如有组合已经不符合条件，就直接跳过（剪枝过程

• TypeScript 实现

function permute(nums: number[]): number[][] {
  const res: number[][] = [];
  const track: number[] = [];
  const backtrack = (nums: number[], track: number[], res: number[][]) => {
    //数字数组 nums，当前的排列 track，和所有排列的数组 res
    if (nums.length === track.length) {
      res.push([...track]); // 创建 track 数组的副本
      return;
    } else {
      for (let i = 0; i < nums.length; i++) {
        if (track.includes(nums[i])) continue; // 如果 track 数组已经包含 nums[i]，则跳过
        track.push(nums[i]);
        backtrack(nums, track, res);
        track.pop(); // 移除最后添加的数字，在下一次循环中，函数需要尝试一个不包含当前数字的新排列。
      }
    }
  };
  backtrack(nums, track, res);

  return res;
}

• Python 实现

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def backtrack():
            if len(nums) == len(track):
                res.append([x for x in track])
                return
            else:
                for num in nums:
                    if num in track:
                        continue
                    track.append(num)
                    backtrack()
                    track.pop()

        res = []
        track = []
        backtrack()
        return res