79. Word Search

source: https://leetcode.com/problems/permutations/

Question

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

回溯法

对于这种找出所有可能性的问题，应该第一时间想到回溯法。

function permute<T = any>(nums: T[]): T[][] {
    const ret: number[][] = [];
    const backtrack = (track: number[]) => {
      if (track.length === nums.length) return ret.push([...track]);
      for (let i = 0; i < nums.length; i++) {
        if (track.includes(i)) continue;
        track.push(i);
        backtrack(track);
        track.pop();
      }
    };
    backtrack([]);
    return ret.map(list => list.map(i => nums[i]));
};

DFS

function permute<T = any>(nums: T[]): T[][] {
    const ret: number[][] = [];
    const dfs = (list: number[], leave: number[]) => {
        if (list.length === nums.length) {
            return ret.push(list);
        }
        leave.forEach(i => {
            dfs([...list, i], leave.filter(v => v !== i));
        });
    };
    dfs([], nums.map((_, i) => i));
    return ret.map(list => list.map(i => nums[i]));
};

总结

全排列是有些其他问题的基础，需要很熟练作为工具方法。