全排列

GitHub跳转原题关系图返回列表

每层选择未使用元素，swap 写法不重不漏。

OJ: leetcodecn

题目 ID: permutations

难度:普及+/提高

标签:回溯DFS递归cpppython

日期: 2026-07-29 13:10

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

返回数组所有全排列。

思路

DFS 回溯，swap 写法将当前数与后面每个数交换，递归后恢复。

代码

cpp
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<vector<int>> permute(vector<int> &nums) {
        vector<vector<int>> ans;
        function<void(int)> dfs = [&](int dep) {
            if (dep == (int)nums.size()) {
                ans.push_back(nums);
                return;
            }
            for (int i = dep; i < (int)nums.size(); i++) {
                swap(nums[dep], nums[i]);
                dfs(dep + 1);
                swap(nums[dep], nums[i]);
            }
        };
        dfs(0);
        return ans;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int &x : a)
        cin >> x;
    for (auto &v : Solution().permute(a)) {
        for (int x : v)
            cout << x << ' ';
        cout << '\n';
    }
    return 0;
}
python
#!/usr/bin/env python3
from typing import List


class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        ans = []

        def dfs(dep):
            if dep == len(nums):
                ans.append(nums[:])
                return
            for i in range(dep, len(nums)):
                nums[dep], nums[i] = nums[i], nums[dep]
                dfs(dep + 1)
                nums[dep], nums[i] = nums[i], nums[dep]

        dfs(0)
        return ans


def main():
    n = int(input())
    a = list(map(int, input().split()))
    for v in Solution().permute(a):
        print(*v)


if __name__ == "__main__":
    main()

复杂度

时间 O(n·n!)，空间 O(n)。

总结

swap 写法省去 visited 数组，是排列生成的标准实现。