全排列

题目

给定一个没有重复数字的序列, 返回其所有可能的全排列.

提示:

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• nums 中的所有整数互不相同

示例

输入: [1, 2, 3]

输出: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

题解

本题为经典的回溯算法, 回溯算法的本质是遍历一颗决策树, 遍历过程中我们肯定会以一定的顺序, 比如先找 1, 再找 2, 最后只能找 3, 此时这这分支找完了, 就会退到上一层, 然后是 3, 最后只能找 2...

JavaScript

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function (nums) {
  const n = nums.length
  const res = []

  const dfs = (track) => {
    if (track.length === n) {
      res.push(track.slice())
      return
    }

    for (const num of nums) {
      if (!track.includes(num)) {
        track.push(num)
        dfs(track)
        track.pop()
      }
    }
  }

  dfs([])

  return res
}

Rust

pub fn permute(nums: Vec<i32>) -> Vec<Vec<i32>> {
    let mut res: Vec<Vec<i32>> = vec![];
    dfs(&nums, &mut vec![], &mut res);
    res
}

fn dfs(nums: &Vec<i32>, track: &mut Vec<i32>, res: &mut Vec<Vec<i32>>) {
    if track.len() == nums.len() {
        res.push(track.to_vec());
        return;
    }

    for num in nums {
        if !track.contains(num) {
            track.push(*num);
            dfs(nums, track, res);
            track.pop();
        }
    }
}