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

1.思路

下面需要重点来看一下什么是回溯算法：

回溯算法是一种通过试错法（试探+回退）解决约束满足问题的通用策略，常用于解决组合优化、排列、子集生成等问题。其核心思想是逐步构建解，若发现当前路径无法达成目标，则回退到上一步尝试其他可能性。

核心思想

  1. 试探：按条件扩展当前解的候选可能性。
  2. 验证：若当前路径不满足约束，立即放弃（剪枝）。
  3. 回退：撤销上一步选择，回到之前的状态继续尝试其他路径。

适用场景

  • 组合问题：如子集、排列、全排列（如 n 选 k）。
  • 约束满足问题：如数独、八皇后、数独。
  • 穷举搜索：当问题规模较小时，回溯可遍历所有可能解。

操作

也就是说解决一个回溯问题，实际上就是一个决策树的遍历过程。在这个过程中只需要思考三个问题： (1)路径：也就是已经做出的选择； (2)选择列表：也就是你当前可以做的选择； (3)结束条件：也就是到达决策树底层，无法再做选择的条件。

回溯算法模板：

result = [] #结果集
path=[] #路径
def backtracking(选择列表):
	# 2.递归终止条件
    if 满足结束条件:
		# 2.1 存放结果
        result.add(满足条件的路径) 
		# 2.2 返回 		
		return
	# 1.选择：在本层集合中遍历元素
	for 选择 in 选择列表:
		# 1.1 处理节点：做出选择
        做选择 
        # 1.2 递归（缩小数据范围。数据范围缩小到一定程度，会触发递归终止条件）
        backtracking(选择列表)
		# 1.3 回溯，撤销选择
        撤销选择

注：核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」。

回溯结构如下图所示：

alt

对回溯算法有了了解之后，就可以套用回溯算法模板完成数字的全排列了，具体思路如下：

alt

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

2.代码

2.1 Python代码

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

    def permute(self, num: List[int]) -> List[List[int]]:
        # write code here
        self.backtracking(num, 0)
        return self.result

    def backtracking(self, num, index):
        # 2.递归终止条件：分枝进入结尾，找到一种排列
        if index == len(num) - 1:
            """
            self.result.append(num)
              num列表的引用添加到result列表中。这意味着result列表现在包含了一个对num列表的引用，而不是num列表的一个独立拷贝。
              因此，如果稍后你修改了num列表，那么这些修改也会反映在result列表中相应的元素上（因为它们引用的是同一个列表）。
            """
            self.result.append(num[:])
            """
                     self.result.append(num[:])：这一行代码使用列表操作[:]来创建一个num列表的浅拷贝（shallow copy），
                       浅拷贝意味着它会复制列表中的元素，但不会复制这些元素所引用的对象。
            """

        # 1. 选择：在本层集合中遍历元素
        for i in range(index, len(num)):
            # 1.1 处理节点:元素互换【如：1,2,3（1放到最前面：1与1交换）；2,1,3（2放到最前面：2与1交换）；3,2,1（3放到最前面：3与1交换）】
            self.swap(num, i, index)
            # 1.2 递归：缩小数列区间【对第i+1个再进行相似的操作（递归），如1,2,3（1固定，再对剩余的2,3进行类似的操作）】
            self.backtracking(num, index + 1)
            # 1.3 回溯，撤销选择:将互换的元素还原【将交换的数据变换回来，再进行下一轮操作】
            self.swap(num, i, index)

    def swap(self, num, i, index):
        num[i], num[index] = num[index], num[i]

2.2 Java代码

import java.util.*;


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

    private void backtracking(int[] num, int index) {
        // 2.递归终止条件：分枝进入结尾，找到一种排列
        if (index == num.length - 1) {
            //2.1 存放结果
            ArrayList<Integer> arrayList = new ArrayList<>();
            for (int v : num) {
                arrayList.add(v);
            }
            result.add(arrayList);
            //2.2 返回
            return;
        }
        //1.选择：在本层集合中遍历元素
        for (int i = index; i < num.length; i++) {
            //1.1 处理节点:元素互换【如：1,2,3（1放到最前面：1与1交换）；2,1,3（2放到最前面：2与1交换）；3,2,1（3放到最前面：3与1交换）】
            swap(num, i, index);
            // 1.2 递归：缩小数列区间【对第i+1个再进行相似的操作（递归），如1,2,3（1固定，再对剩余的2,3进行类似的操作）】
            backtracking(num, index + 1);
            //1.3 回溯，撤销选择:将互换的元素还原【将交换的数据变换回来，再进行下一轮操作】
            swap(num, i, index);
        }
    }

    private void swap(int[] num, int i, int j) {
        int tmp = num[i];
        num[i] = num[j];
        num[j] = tmp;
    }

    ArrayList<ArrayList<Integer>> result = new ArrayList<>(); //结果集

}

2.3 Go代码

package main

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

var result [][]int

func backtracking(num []int, index int) {
	// 2.递归终止条件：分枝进入结尾，找到一种排列
	if index == len(num)-1 {
		//2.1 存放结果
		tmp := append([]int{}, num...) //将num结果复制一份(新建一个切片，如果是引用原来切片，是地址引用，num内容改变时，result数据也会发生改变)
		result = append(result, tmp)
		//2.2 返回
		return
	}

	//1.选择：在本层集合中遍历元素
	for i := index; i < len(num); i++ {
		//1.1 处理节点:元素互换【如：1,2,3（1放到最前面：1与1交换）；2,1,3（2放到最前面：2与1交换）；3,2,1（3放到最前面：3与1交换）】
		swap(num, i, index)
		// 1.2 递归：缩小数列区间【对第i+1个再进行相似的操作（递归），如1,2,3（1固定，再对剩余的2,3进行类似的操作）】
		backtracking(num, index+1)
		//1.3 回溯，撤销选择:将互换的元素还原【将交换的数据变换回来，再进行下一轮操作】
		swap(num, i, index)
	}
}

func swap(num []int, i int, index int) {

	num[i], num[index] = num[index], num[i]
}

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