秒懂【全排列】！回溯算法一步步拆解。

1.思路

通过回溯法实现数字项的全排列，要特别留意重复数字的处理。具体思路如下：

alt

alt

参考回溯算法模板，进行以下操作：

遍历每一个元素，以该元素作为开头的数字数列。首先选取该数字，并标记该数字已经使用过；再递归选择其他数字；撤销该数字，让其他数字作为开头。缩小数字区间：该元素已经使用过；当前元素与前一个元素一样，且前一个已经使用过。

递归终止条件：选择的数字已经达到n个（数列的长度），则保存选择数字组成的序列，并返回。

2.代码

如果文字描述的不太清楚，你可以参考视频的详细讲解：B站@好易学数据结构

2.1 Python代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param num int整型一维数组
# @return int整型二维数组
#
class Solution:
    def __init__(self):
        self.result = []  # 结果集
        self.path = []  # 路径
        self.mark = []  # 标记

    def permuteUnique(self, num: List[int]) -> List[List[int]]:
        # write code here
        self.mark = [False] * len(num)
        num.sort()
        self.backtracking(num)
        return self.result

    def backtracking(self, num):
        # 2. 递归终止条件：已经找到一条路径（路径数组满了）,则加入到输出列表
        if len(self.path) == len(num):
            # 2.1 存放结果
            self.result.append(self.path[:])  # 使用浅拷贝（shallow copy）：复制值 并非引用
            # 2.2  返回
            return

        for i in range(len(num)):
            # 1.4 剪枝
            # 1.4.1 元素已经使用过则不需要再加入了
            if self.mark[i]:
                continue
            # 1.4.2 当前的元素num[i]与同一层的前一个元素num[i-1]相同且num[i-1]已经用过了
            if i >= 1 and num[i] == num[i - 1] and self.mark[i - 1]:
                continue

            # 1.1 处理节点 （选取数字）
            self.path.append(num[i])  # 加入路径
            self.mark[i] = True  # 标记为使用过
            # 1.2 递归（选择其他数字）
            self.backtracking(num)
            # 1.3 回溯，撤销选择
            self.path = self.path[: len(self.path) - 1]
            self.mark[i] = False

2.2 Java代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param num int整型一维数组
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> permuteUnique (int[] num) {
        // write code here
        result = new ArrayList<>();
        path = new ArrayList<>();
        mark = new boolean[num.length];
        Arrays.sort(num);
        backtracking(num);
        return result;
    }

    private void backtracking(int[] num) {
        // 2.递归终止条件：已经找到一条路径（路径数组满了）,则加入到输出列表
        if (path.size() == num.length) {
            //2.1 存放结果
            ArrayList<Integer> tmp = new ArrayList<>(path);//复制元素
            result.add(tmp);
            // result.add(path)   todo :错误写法，需要按照以上写法转化
            //2.2 返回
            return;
        }

        for (int i = 0; i < num.length; i++) {
            //1.4 剪枝
            //1.4.1 元素已经使用过则不需要再加入了
            if (mark[i]) {
                continue;
            }
            //1.4.2 当前的元素num[i]与同一层的前一个元素num[i-1]相同且num[i-1]已经用过了
            if ((i >= 1) && (num[i] == num[i - 1]) && mark[i - 1]) {
                continue;
            }
            //1.1 处理节点 （选取数字）
            path.add(num[i]);
            mark[i] = true;
            // 1.2 递归（选择其他数字）
            backtracking(num);
            //1.3 回溯，撤销选择
            path.remove(path.size() - 1);
            mark[i] = false;
        }
    }

    ArrayList<ArrayList<Integer>> result;//结果集
    ArrayList<Integer> path;//路径
    boolean[] mark;
}

2.3 Go代码

package main

import (
	"sort"
)

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param num int整型一维数组
 * @return int整型二维数组
 */
func permuteUnique(num []int) [][]int {
	// write code here
	result = make([][]int, 0)
	path = make([]int, 0)
	mark = make([]bool, len(num))
	sort.Ints(num)
	backtracking(num)
	return result
}

func backtracking(num []int) {
	// 2.递归终止条件：已经找到一条路径（路径数组满了）,则加入到输出列表
	if len(path) == len(num) {
		//2.1 存放结果
		tmp := append([]int{}, path...) //新建一个切片，如果是引用原来切片，是地址引用，path内容改变时，result数据也会发生改变
		result = append(result, tmp)
		//2.2 返回
		return
	}

	//1.选择：在本层集合中遍历元素
	for i := 0; i < len(num); i++ {
		//1.4 剪枝
		//1.4.1 元素已经使用过则不需要再加入了
		if mark[i] {
			continue
		}
		//1.4.2 当前的元素num[i]与同一层的前一个元素num[i-1]相同且num[i-1]已经用过
		if (i >= 1) && (num[i-1] == num[i]) && mark[i-1] {
			continue
		}

		//1.1 处理节点 （选取数字）
		path = append(path, num[i])
		mark[i] = true
		// 1.2 递归（选择其他数字）
		backtracking(num)
		//1.3 回溯，撤销选择
		path = path[:len(path)-1]
		mark[i] = false
	}
}

var (
	result [][]int //结果集
	path   []int   //路径
	mark   []bool
)

如果上面的代码理解的不是很清楚，你可以参考视频的详细讲解：B站@好易学数据结构