LeetCode 46 Permutations

Tag: LeetCode 回溯法 Posted on 2020-06-07 11:10:47 Edited on 2020-06-07 11:12:48 Views: 171

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!)

Links: Leetcode-416-Partition-Equal-Subset-Sum