【LeetCode-46】全排列

问题

给定一个没有重复数字的序列，返回其所有可能的全排列。

示例

输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

解答1：回溯（容易理解，效率较低）

class Solution {
vector<vector<int>> res {};
vector<int> cur {};
public:
    vector<vector<int>> permute(vector<int>& nums) {
        backTrace(nums);
        return res;
    }

    void backTrace(vector<int>& nums) {
        if (nums.size() == cur.size()) {
            res.push_back(cur);
            return;
        }
        for (int i=0; i<nums.size(); i++) {
            if (find(cur.begin(), cur.end(), nums[i]) == cur.end()) {
                cur.push_back(nums[i]);
                backTrace(nums);
                cur.pop_back();
            }
        }
    }
};

重点思路

回溯递归需要确定两个重点：1. 递归终点，本题为cur达到nums长度时；2. 状态的更新与还原，本题通过push_back和pop_back来分别实现。这个实现很容易理解，不多加赘述。

解答2：回溯（STL实现）

class Solution {
vector<vector<int>> res {};
public:
    vector<vector<int>> permute(vector<int>& nums) {
        c(nums, 0);
        return res;
    }

    void backTrace(vector<int>& nums, int index) {
        if (index == nums.size()) {
            res.push_back(nums);
            return;
        }
        for (int i = index; i < nums.size(); ++i) {
            swap(nums[index], nums[i]);
            backTrace(nums, index+1);
            swap(nums[index], nums[i]);
        }
    }
};

重点思路

该实现为C++中的STL实现方法。index表示更新次数，到nums的size说明该轮所有更新已完成，即递归终点。通过swap进行状态的更新与还原。

要理解这个算法最好举一个例子。如输入[1,2,3,4]，由于初始化为i=index，swap无效果，第一个输出为原数组[1,2,3,4]。for循环完成，随后递归层数-1，此时i=3，index更新为4，则交换3、4，输出[1,2,4,3]。for循环完成，递归层数再-1，此时i=2，index=3，输出[1,3,2,4]。随后i=3，index=4，输出[1,3,4,2]。以此类推，上述说明中省略了i=index的步骤。

【LeetCode-46】全排列

原文：https://www.cnblogs.com/tmpUser/p/14385656.html