当前位置：首页 > article >正文

Leetcode 46. 全排列排列型回溯 C++实现

article 2025/3/6 21:07:46

Leetcode 46. 全排列

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

算法：

创建二维返回数组 ans ，和临时数组 path ，on_path 。

进入 dfs 函数，当 i==n 时，即已经排列完毕，则可以 return 。从 0 到 n 遍历，如果没选过就加入 path 中，并且将 on_path 设置成 true 表示该数字已经被挑选。进入下一层递归。下一层递归完毕返回该层后，将该层挑选的数字所对应的 on_path 重置（再次设置成 false ，即未被挑选状态），恢复现场。

代码：

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;// 返回数组ans
        int n = nums.size();
        vector<int> path(n),on_path(n);// 临时数组path
        auto dfs = [&](auto &&dfs,int i){
            if(i == n){
                ans.emplace_back(path);
                return ;
            }
            for(int j = 0;j < n;j++){
                if(!on_path[j]){
                    path[i] = nums[j];
                    on_path[j] = true;
                    dfs(dfs,i+1);
                    on_path[j] = false;
                }
            }
        };
        dfs(dfs,0);// 递归入口
        return ans;
    }
};

查看全文

http://www.kler.cn/a/280351.html