leetcode46：全排列

题目链接

leetcode

题目描述

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

C++ 代码

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

/*
    回溯

    从前往后，一位一位枚举，每次选择一个没有被使用的数。
    选好之后，将该数的状态改为 “已被使用”，同时将该数记录在相应位置，然后递归。
    细节：递归返回时，将该数的状态改为 “未被使用”，并将该数从相应位置上删除。

    时间复杂度：O(n*n!)
        其中 n 是数字的数量。
        对于每个数字，都有两种选择：使用或不使用，共有 n! 种可能的排列。
        因此，总的时间复杂度是 O(n*n!)。
    空间复杂度：O(n)
        除答案数组以外，在递归过程中需要为每一层递归函数分配栈空间，
        所以空间取决于递归的深度，递归调用深度为 O(n)。
*/
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        result.clear();
        path.clear();
        visited = vector<bool>(nums.size(), false);

        dfs(nums);
        return result;
    }

    void dfs(vector<int>& nums) {
        // 结束条件：找到一组排列
        if (path.size() == nums.size()) {
            result.push_back(path);
            return;
        }

        for (int i = 0; i < nums.size(); i++) {
            // 若当前数字已经被访问，则跳过
            if (visited[i]) {
                continue;
            }

            // 选择
            path.push_back(nums[i]);
            visited[i] = true;
            // 递归下一层
            dfs(nums);
            // 撤销选择，回溯
            path.pop_back();
            visited[i] = false;
        }
    }

private:
    vector<vector<int>> result; // 结果数组
    vector<int> path;           // 记录回溯的路径
    vector<bool> visited;       // 标记数组：标记路径中的元素，避免重复使用
};

// 辅助函数：打印数组
void printArray(vector<int>& nums) {
	cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if (i != nums.size()-1) {
            cout << ",";
        }
    }
    cout << "]" << endl;
}

// 辅助函数：打印二维数组
void printArray(const vector<vector<int>>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << "[";
        for (size_t j = 0; j < nums[i].size(); j++) {
            cout << nums[i][j];
            if (j != nums[i].size() - 1) cout << ",";
        }
        cout << "]";
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]" << endl;
}

int main() {
    Solution solution;
    vector<vector<int>> nums_cases = {
        {1,2,3},
        {0,1},
        {1},
    };

    for (size_t i = 0; i < nums_cases.size(); i++) {
        auto& nums = nums_cases[i];
        cout << "Input: ";
        printArray(nums);

        vector<vector<int>> result = solution.permute(nums);
        cout << "Output: ";
        printArray(result);
    }

    return 0;
}