46

46. Permutations (Medium)

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.

Companies: Bloomberg, Apple, Goldman Sachs

Related Topics:
Array, Backtracking

Similar Questions:

• Next Permutation (Medium)
• Permutations II (Medium)
• Permutation Sequence (Hard)
• Combinations (Medium)

Solution 1. DFS

For a particular DFS level, let start be the index of element we manipulate in this level.

We swap nums[start] with a digit whose index >= start.

After the swap, we DFS one step further, i.e. dfs(nums, start + 1).

Once the children DFS returns, we recover the array by swapping them back.

The exit condition of DFS is when the start index points to the last digit, then we can push the current nums into answers.

The initial call is dfs(nums, 0).

Note that:

1. This function doesn't care whether the nums is sorted.
2. The permutations generated is NOT in lexigraphical order. For example, if input is [1,2,3], then output is [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,2,1],[3,1,2]]

// OJ: https://leetcode.com/problems/permutations/
// Author: github.com/lzl124631x
// Time: O(N!)
// Space: O(N)
class Solution {
public:
    vector<vector<int>> permute(vector<int>& A) {
        vector<vector<int>> ans;
        int N = A.size();
        function<void(int)> dfs = [&](int start) {
            if (start == N) {
                ans.push_back(A);
                return;
            }
            for (int i = start; i < N; ++i) {
                swap(A[i], A[start]);
                dfs(start + 1);
                swap(A[i], A[start]);
            }
        };
        dfs(0);
        return ans;
    }
};

Solution 2. Use NextPermutation

Reuse the solution for 31. Next Permutation (Medium).

// OJ: https://leetcode.com/problems/permutations/
// Author: github.com/lzl124631x
// Time: O(N!)
// Space: O(1)
class Solution {
    bool nextPermutation(vector<int>& A) {
        int N = A.size(), i = N - 1;
        while (i - 1 >= 0 && A[i - 1] >= A[i]) --i; // find the first element of a descending subarray from the end.
        reverse(begin(A) + i, end(A)); // reverse this descending subarray
        if (i == 0) return false;
        swap(*upper_bound(begin(A) + i, end(A), A[i - 1]), A[i - 1]); // swap A[i-1] with the first element greater than `A[i-1]` in the subarray.
        return true;
    }
public:
    vector<vector<int>> permute(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans { nums };
        while (nextPermutation(nums)) ans.push_back(nums);
        return ans;
    }
};