LeetCode46. Permutations（递归 / 回溯）

LeetCode46. Permutations（递归 / 回溯）

• Medium
• Accepted：359,004
• Submissions：661,126

Given a collection of distinct integers, return all possible permutations.

Example:

Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

链接

https://leetcode.com/problems/permutations

题意

给定一个不同整数的集合，返回所有可能的排列。

题解

经典的组合问题，和之前的LeetCode17. Letter Combinations of a Phone Number（递归 / 回溯）有点类似。

假设nums表示整数集合，Perms(nums)表示整数的排列，那么Perms(nums[0...n-1]) = {nums[i]} + Perms(nums[{0...n-1} - i])。

时间复杂度$T(n) = n * T(n-1) + O(1)$，$O(n!)$。

代码

class Solution {
private:
    vector<vector<int> > ans; // 保存答案
    vector<bool> vis; // 判断是否已经使用
    void solve(const vector <int> & nums, int index, vector<int> & p)
    {
        if (index == nums.size())
        {
            ans.push_back(p);
            return ;
        }
        for (int i = 0; i < nums.size(); ++i)
        {
            if (!vis[i])
            {
                p.push_back(nums[i]);
                vis[i] = true;
                solve(nums, index + 1, p);
                p.pop_back(); // 回溯
                vis[i] = false;
            }
        }
    }
public:
    vector<vector<int>> permute(vector<int>& nums) {
        ans.clear();
        if (nums.empty())
            return ans;
        vector <int> p;
        vis = vector<bool> (nums.size(), false);
        solve(nums, 0, p);
        return ans;
    }
};

• Runtime: 3 ms, faster than 79.22% of C++ online submissions for Permutations.
• Memory Usage: 7.7 MB, less than 56.70% of C++ online submissions for Permutations.

class Solution
{
public:
    vector<vector<int>> permute(vector<int> &nums)
    {
        result.clear();
        n = nums.size();
        if (n == 0)
            return result;
        getSets(nums, 0);
        return result;
    }
private:
    int n;
    vector<vector<int>> result;

    void getSets(vector<int> &nums, int idx)
    {
        if (idx == n)
        {
            result.push_back(nums);
            return ;
        }
        else if (idx < n)
        {
            // 交换位置，每次有 n - idx 个选择
            for (int i = idx; i < n; ++i)
            {
                swap(nums[i], nums[idx]);
                getSets(nums, idx + 1);
                swap(nums[i], nums[idx]);
            }
        }
    }
};