46.全排列

46.全排列

#回溯 2024-09-20

class Solution {
private:
    set<int> recordFirst;
    vector<vector<int>> result;
    vector<int> path;
public:
    void backtrace(vector<int>& nums){
        if(path.size() == nums.size()){
            result.push_back(path);
            return;
        }

        for(int i = 0; i < nums.size(); i++){
            if(recordFirst.find(nums[i]) != recordFirst.end()){
                continue;
            }

            path.push_back(nums[i]);
            recordFirst.insert(nums[i]);
            backtrace(nums);
            recordFirst.erase(nums[i]);
            path.pop_back();
        }
    }

    vector<vector<int>> permute(vector<int>& nums) {
        backtrace(nums);
        return result;
    }
};

我们简单捋一下思路，这道题相当简单。

从此题的题意可以看出，我们每次必须从数组的开头遍历，那我们就不需要像前面的组合题那样需要一个参数来记录当前位置，以方便下一个栈能够找到从哪里继续开始。

也正因为这个缘故，我们必须判断已加入到路径中的元素不可再重复。用一个全局的记录项 recordFirst，借此来去重。我们不是同一栈的去重，而是和前面所有被加入路径的元素进行去重，那就得有之前的信息，全局记录项就是恰当的。