算法题/排列组合：不含重复数字的排列

题目

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

示例1：

输入：nums=[1, 2, 3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
解释：无

示例2：

输入：nums=[0,1]
输出：[[0,1],[1,0]]
解释：无

解答

Java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class Solution {

    public List<List<Integer>> permute(int[] nums) {
        int len = nums.length;
        // 使用一个动态数组保存所有可能的全排列
        List<List<Integer>> res = new ArrayList<>();
        if (len == 0) {
            return res;
        }
        boolean[] used = new boolean[len];
        //deque为双端队列，用来实现一个栈
        //path为路径
        Deque<Integer> path = new ArrayDeque<>(len);
        dfs(nums, len, 0, path, used, res);
        return res;
    }

    private void dfs(int[] nums, int len, int depth, Deque<Integer> path, boolean[] used, List<List<Integer>> res) {
        if (depth == len) {
            //变量 path 所指向的列表 在深度优先遍历的过程中只有一份 ，
            //深度优先遍历完成以后，回到了根结点，成为空列表。
	    //在 Java 中，参数传递是 值传递，对象类型变量在传参的过程中，复制的是变量的地址
	    //这些地址被添加到 res 变量，但实际上指向的是同一块内存地址
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < len; i++) {
            if (used[i]) {
                break;
            }
            path.addLast(nums[i]);
            used[i] = true;
            dfs(nums, len, depth + 1, path, used, res);
            used[i] = false;
            path.removeLast();
        }
    }
    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        Solution solution = new Solution();
        List<List<Integer>> lists = solution.permute(nums);
    }
}

JavaScript

class Solution {
  permute(nums) {
    const len = nums.length;
    const res = [];
    if (len === 0) {
      return res;
    }
    const used = new Array(len).fill(false);
    const path = [];
    this.dfs(nums, len, 0, path, used, res);
    return res;
  }

  dfs(nums, len, depth, path, used, res) {
    if (depth === len) {
      res.push([...path]);
      return;
    }
    for (let i = 0; i < len; i++) {
      if (used[i]) {
        continue;
      }
      path.push(nums[i]);
      used[i] = true;
      this.dfs(nums, len, depth + 1, path, used, res);
      used[i] = false;
      path.pop();
    }
  }
}

const nums = [1, 2, 3];
const solution = new Solution();
const lists = solution.permute(nums);

Python

from typing import List

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def dfs(nums, depth, path, used, res):
            if depth == len(nums):
                res.append(path[:])
                return
            for i in range(len(nums)):
                if used[i]:
                    continue
                path.append(nums[i])
                used[i] = True
                dfs(nums, depth + 1, path, used, res)
                used[i] = False
                path.pop()

        res = []
        if len(nums) == 0:
            return res
        used = [False] * len(nums)
        path = []
        dfs(nums, 0, path, used, res)
        return res

nums = [1, 2, 3]
solution = Solution()
lists = solution.permute(nums)

Go

package main

import "fmt"

func permute(nums []int) [][]int {
	var res [][]int
	len := len(nums)
	if len == 0 {
		return res
	}
	used := make([]bool, len)
	path := []int{}
	dfs(nums, len, 0, path, used, &res)
	return res
}

func dfs(nums []int, len, depth int, path []int, used []bool, res *[][]int) {
	if depth == len {
		*res = append(*res, append([]int(nil), path...))
		return
	}
	for i := 0; i < len; i++ {
		if used[i] {
			continue
		}
		path = append(path, nums[i])
		used[i] = true
		dfs(nums, len, depth+1, path, used, res)
		used[i] = false
		path = path[:len(path)-1]
	}
}

func main() {
	nums := []int{1, 2, 3}
	lists := permute(nums)
	fmt.Println(lists)
}