Permutations

Source

• lintcode: (15) Permutations

Given a list of numbers, return all possible permutations.

Example
For nums [1,2,3], the permutaions are:

[

    [1,2,3],

    [1,3,2],

    [2,1,3],

    [2,3,1],

    [3,1,2],

    [3,2,1]

]

Challenge
Do it without recursion

题解

排列常见的有数字全排列，字符串排列等。

使用之前subsets的模板，但是在取结果时只能取list.size() == nums.size()的解，且在添加list元素的时候需要注意除重。

C++

class Solution {
public:
    /**
     * @param nums: A list of integers.
     * @return: A list of permutations.
     */
    vector<vector<int> > permute(vector<int> nums) {
        vector<vector<int> > result;
        if (nums.empty()) {
            return result;
        }

        vector<int> list;
        backTrack(result, list, nums);

        return result;
    }

private:
    void backTrack(vector<vector<int> > &result, vector<int> &list, \
                   vector<int> &nums) {
        if (list.size() == nums.size()) {
            result.push_back(list);
            return;
        }

        for (int i = 0; i != nums.size(); ++i) {
            // remove the element belongs to list
            if (find(list.begin(), list.end(), nums[i]) != list.end()) {
                continue;
            }
            list.push_back(nums[i]);
            backTrack(result, list, nums);
            list.pop_back();
        }
    }
};

源码分析

在除重时使用了标准库find(不可使用时间复杂度更低的binary_search，因为list中元素不一定有序)，时间复杂度为 $O(N)$, 也可使用hashmap记录nums中每个元素是否被添加到list中，这样一来空间复杂度为 $O(N)$, 查找的时间复杂度为 $O(1)$.

在list.size() == nums.size()时，已经找到需要的解，及时return避免后面不必要的for循环调用开销。

使用回溯法解题的关键在于如何确定正确解及排除不符条件的解(剪枝)。