全排列与回溯算法详解：LeetCode 经典题目解析 | 极客日志

编程语言算法

全排列与回溯算法详解：LeetCode 经典题目解析

本文介绍全排列算法的定义、特点及实现方式，涵盖递归法与 STL 函数。详细解析了 LeetCode 中的全排列、子集、带重复元素的全排列、括号生成及组合问题，提供 C++ 与 Java 代码示例，并探讨剪枝优化与注意事项。

Kubernet发布于 2026/3/22更新于 2026/4/164 浏览

全排列与回溯算法详解：LeetCode 经典题目解析

全排列的简要总结

全排列（Permutation）是数学中一个经典的问题，指的是从一组元素中，将所有元素按任意顺序排列形成的所有可能序列。

特点

输入条件：
- 给定一组互异的元素（通常为数组或字符串）。
- 例如：[1, 2, 3] 的全排列。
输出结果：
- 输出所有元素的排列组合。
数量公式：
- 对于 n 个互异元素，其全排列数量为 n!（阶乘）。
- 例如：n = 3 时，全排列数量为 3! = 6。

例如：[1, 2, 3] 的全排列是：

[1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1]

实现方式

1. 递归法

通过递归交换或回溯实现：

#include <iostream>
#include <vector>
using namespace std;

void backtrack(vector<int>& nums, int start, vector<vector<int>>& result) {
    if (start == nums.size()) {
        result.push_back(nums);
        return;
    }
    for (int i = start; i < nums.size(); i++) {
        swap(nums[start], nums[i]); // 交换当前元素
        backtrack(nums, start + 1, result); // 递归处理子问题
        (nums[start], nums[i]); 
    }
}

{
    vector<> nums = {, , };
    vector<vector<>> result;
    (nums, , result);
     ( & perm : result) {
         ( num : perm) {
            cout << num << ;
        }
        cout << endl;
    }
     ;
}

极客日志微信公众号二维码

更多推荐文章

相关免费在线工具

加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。在线工具，加密/解密文本在线工具，online
Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。在线工具，Base64 字符串编码/解码在线工具，online
Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。在线工具，Base64 文件转换器在线工具，online
Markdown转HTML
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。在线工具，Markdown转HTML在线工具，online
HTML转Markdown
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。在线工具，HTML转Markdown在线工具，online
JSON 压缩
通过删除不必要的空白来缩小和压缩JSON。在线工具，JSON 压缩在线工具，online

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> nums = {1, 2, 3};
    do {
        for (int num : nums) {
            cout << num << " ";
        }
        cout << endl;
    } while (next_permutation(nums.begin(), nums.end()));
    return 0;
}

import java.util.*;

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] visited;

    public void dfs(int[] nums, List<Integer> path) {
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
        } else {
            for (int i = 0; i < nums.length; i++) {
                if (!visited[i]) {
                    path.add(nums[i]);
                    visited[i] = true; // 标记，下次不能再选
                    dfs(nums, path);
                    visited[i] = false; // 回溯复原
                    path.remove(path.size() - 1);
                }
            }
        }
    }

    public List<List<Integer>> permute(int[] nums) {
        visited = new boolean[nums.length];
        dfs(nums, path);
        return res;
    }
}

import java.util.*;

class Solution {
    List<List<Integer>> ret = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public void dfs(int[] nums, int pos) {
        if (pos == nums.length) {
            ret.add(new ArrayList<>(path));
            return;
        }
        // 选
        path.add(nums[pos]);
        dfs(nums, pos + 1);
        path.remove(path.size() - 1); // 恢复现场
        // 不选
        dfs(nums, pos + 1);
    }

    public List<List<Integer>> subsets(int[] nums) {
        dfs(nums, 0);
        return ret;
    }
}

import java.util.*;

class Solution {
    List<Integer> path = new ArrayList<>();
    List<List<Integer>> ret = new ArrayList<>();
    boolean[] visited;

    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums); // 先进行排序
        visited = new boolean[nums.length];
        dfs(nums);
        return ret;
    }

    public void dfs(int[] nums) {
        if (path.size() == nums.length) {
            ret.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            // 剪枝
            if (!visited[i] && (i == 0 || nums[i] != nums[i - 1] || visited[i - 1])) {
                path.add(nums[i]);
                visited[i] = true;
                dfs(nums);
                path.remove(path.size() - 1); // 恢复现场
                visited[i] = false;
            }
        }
    }
}

import java.util.*;

class Solution {
    List<String> str = new ArrayList<>();

    public void dfs(String it, int left, int right) {
        if (left == 0) { // 做括号全部用完
            while (right > 0) {
                it += ")";
                right--;
            }
            str.add(it);
            return;
        }
        it += "("; // 插入左括号
        dfs(it, left - 1, right);
        it = it.substring(0, it.length() - 1); // 回溯，回复现场
        if (right > left) { // 右括号剩余必须比左括号多
            it += ")";
            dfs(it, left, right - 1);
            it = it.substring(0, it.length() - 1); // 回溯
        }
    }

    public List<String> generateParenthesis(int n) {
        String it = "";
        int left = n;
        int right = n;
        it += "("; // 左边先插入一个（，避免第一个就是）的错误
        left--;
        dfs(it, left, right);
        return str;
    }
}

import java.util.*;

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> flag = new ArrayList<>();

    public void dfs(int n, int k, int first) {
        if (k == 0) {
            res.add(new ArrayList<>(flag));
            return;
        }
        for (int i = first; i <= n; i++) {
            flag.add(i);
            dfs(n, k - 1, i + 1);
            flag.remove(flag.size() - 1);
        }
    }

    public List<List<Integer>> combine(int n, int k) {
        dfs(n, k, 1);
        return res;
    }
}