46.全排列.md

46.全排列

解题思路

分治

由于每个元素都不一致，因此，每次从所有元素中选择一个不同的元素进行填充，直到没有元素可选，即可完成所有排列

function permute(nums: number[]): number[][] {
    const size = nums.length
    const list: number[][] = []
    const pick = (index: number, selected: number[]) => {
        if (index > size - 1) {
            list.push(selected)
        } else {
            for (let i = 0; i < size; i++) {
                if (selected[i] === null) {
                    const _selected = Array.from(selected)
                    _selected[i] = nums[index]
                    pick(index + 1, _selected)
                }
            }
        }
    }
    pick(0, new Array(size).fill(null))
    return list
};

回溯法

按深度优先的方式，每选完一个，便对该元素进行缓存，直至选完所有元素，则回退到下一个节点进行选择

function permute(nums: number[]): number[][] {
    const size = nums.length
    const list: number[][] = []
    const vis: boolean[] = []
    const pick = (selected: number[]) => {
        if (selected.length === size) {
            list.push(selected.slice())
        } else {
            for (let i = 0; i < size; i++) {
                if (vis[nums[i]]) continue
                selected.push(nums[i])
                vis[nums[i]] = true
                pick(selected)
                vis[nums[i]] = false
                selected.pop()
            }
        }
    }
    pick([])
    return list
};