LeetCode46——全排列问题

题目描述

给定一个不含重复数字的数组 nums ，返回其所有可能的全排列 。你可以按任意顺序返回答案。
46. 全排列
典型的搜索问题，采用回溯，此类问题模板如下，官方解答如下，主要首先要判断结束条件，然后每步需要交换位置。

class Solution {
public:
    void backtrack(vector<vector<int>>& res, vector<int>& output, int first, int len){
        // 所有数都填完了
        if (first == len) {
            res.emplace_back(output);
            return;
        }
        for (int i = first; i < len; ++i) {
            // 动态维护数组
            swap(output[i], output[first]);
            // 继续递归填下一个数
            backtrack(res, output, first + 1, len);
            // 撤销操作
            swap(output[i], output[first]);
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int> > res;
        backtrack(res, nums, 0, (int)nums.size());
        return res;
    }
};

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/permutations/solution/quan-pai-lie-by-leetcode-solution-2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

也可以记录哪些元素访问过来解决。

class Solution {
public:
    void dfs(vector<int> &nums, vector<vector<int>> &ans, vector<int> &temp, std::unordered_map<int, int> &d) {
        if (temp.size() == nums.size()) {
            ans.push_back(temp);
            return;
        }

        for (int i = 0; i < nums.size(); i++) {
            // vector<int> temp;
            // std::unordered_map<int, int> d;
            if (d.find(nums[i]) == d.end() || d[nums[i]] == 0) {
                d[nums[i]] = 1;
                temp.push_back(nums[i]);
                dfs(nums, ans, temp, d);
                d[nums[i]] = 0;
                temp.pop_back();

            }
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;
        std::unordered_map<int, int> d;
        vector<int> temp;
        dfs(nums, ans, temp, d);
        return ans;

    }
};