LeetCode 46 Permutations

标签: 回溯法 LeetCode 发布于:2020-06-07 11:10:47 编辑于:2022-02-22 10:54:42 浏览量:1400

概述

https://leetcode.com/problems/permutations/

第一次做的时候的笔记

第一次提交

class Solution {
public:
    vector<vector<int>> res;
    vector<vector<int>> permute(vector<int>& nums) {
        vector<int> track;
        backtrack(nums, track);
        return res;
    }
    
private:
    void backtrack(vector<int>& nums, vector<int>& track) {
        // Deal with the end case
        if(track.size()==nums.size()) {
            res.push_back(track);
            return;
        }
        for(auto num:nums){
            // Check whether the current num has been used
            if(find(track.begin(), track.end(), num)!=track.end()){ // Has been used
                continue;
            }
            track.push_back(num);
            backtrack(nums, track);
            track.pop_back();
        }
    }
};

第二次提交

针对第一次提交,其中的检查路径中是否已经包含该节点的方式可以改进。

因为我们是按顺序访问 nums 的,因此只需要记录一下当前访问到那个节点就好,之后循环遍历的时候直接从该节点开始。

除此之外,我们知道 track 的用途是记录当前已访问过的节点,其实直接用 nums 存就好,我们就按照访问顺序去存储,访问该路径后回溯回来就好。

class Solution {
public:
    vector<vector<int>> res;
    vector<vector<int>> permute(vector<int>& nums) {
        backtrack(nums, 0);
        return res;
    }
    
private:
    void backtrack(vector<int>& nums, int startIndex) {
        // Deal with the end case
        if(startIndex >= nums.size()) {
            res.push_back(nums);
            return;
        }
        for(int i=startIndex;i<nums.size();++i){
            swap(nums[startIndex], nums[i]);
            backtrack(nums, startIndex+1);
            swap(nums[startIndex], nums[i]);
        }
    }
};

分析总结

在该题目中,我们对搜索树进行了剪枝,每向下一层少一种选择,则总的路径个数为(设 n 为 nums 的尺寸):n! 复杂度也即 O(n!)

2022年2月22日时的笔记

class Solution {
public:
    vector<vector<int>> ans;
    vector<vector<int>> permute(vector<int>& nums) {
        vector<bool> visited(nums.size());
        vector<int> path;
        backtrack(nums, path, visited);
        return ans;
    }
    
    void backtrack(vector<int>& nums, vector<int>& path, vector<bool>& visited) {
        if (path.size() == nums.size()) {
            ans.push_back(path);
            return;
        }
        for (int i = 0; i < visited.size(); i ++) {
            if (!visited[i]) {
                visited[i] = true;
                path.push_back(nums[i]);
                backtrack(nums, path, visited);
                path.pop_back();
                visited[i] = false;
            }
        }
    }
};

遍历整棵决策树,因此时间复杂度 O(n! * n) = O(n!)。

未经允许,禁止转载,本文源站链接:https://iamazing.cn/