0046. Permutations

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Example 1:

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

Example 2:

Input: nums = [0,1]
Output: [[0,1],[1,0]]

Example 3:

Input: nums = [1]
Output: [[1]]

Constraints:

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• All the integers of nums are unique.

Analysis

Traditional DFS

There are two recursive ways to solve this problem. One way is the traditional DFS with the help of additional memory to record any existing configuration. For each iteration, we use an index to locate which index we are going to place our number, and the base case is when this index reaches the end. When placing our number at this index, we should try out all the numbers from nums[0] to nums[end], and compare them with the current visited memory to decide if we can put that number at the index. This process for each iteration will take up $O(n)$ complexity, and there will be n! results at the bottom level, so the total time complexity is $O(n \times n!)$.

Using Swap

We could also use a different way to generate each configuration by using a swap operation. For each iteration, we require an index to represent: from nums[0] to nums[i] we will maintain the current order, and starting from i + 1 we will start to swap with each j where j is in [i + 1, n), so that it helps eliminate the need for visited memory. However, the time complexity is still $O(n \times n!)$.

Code

Method 1

class Solution {
public:
    vector<vector<int>> ret;
    vector<vector<int>> permute(vector<int>& nums) {
        helper ({}, nums);
        return ret;
    }
    void helper (vector<int> curr, vector<int>& nums)
    {
        if (curr.size () == nums.size ())
            ret.push_back (curr);
        else
        {
            unordered_set<int> s(curr.begin (), curr.end ());
            for (int i = 0; i < nums.size (); ++i)
            {
                if (s.find (nums[i]) != s.end ())
                    continue;
                else
                {
                    curr.push_back (nums[i]);
                    helper (curr, nums);
                    curr.pop_back ();
                }
            }
        }
    }
};

Code 2

class Solution {
public:
    vector<vector<int>> res;
    void h(vector<int> curr, int index) {
        if (index == curr.size()) {
            res.push_back(curr);
            return;
        }
        for (int i = index; i < curr.size(); ++i) {
            swap(curr[i], curr[index]);
            h(curr, index + 1);
            swap(curr[i], curr[index]);
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        h(nums, 0);
        return res;
    }
};