46. Permutations
1. Description
Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.
2. Example
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]]
3. Constraints
- 1 <= nums.length <= 6
- -10 <= nums[i] <= 10
- All the integers of nums are unique.
4. Solutions
Backtracking
n = nums.size()
Time complexity: O(nn!)
Space complexity: O(n)
class Solution {
public:
vector<vector<int>> permute(vector<int> nums) {
vector<vector<int>> permutations;
search_permutations(permutations, nums, 0);
return permutations;
}
private:
void search_permutations(
vector<vector<int>> &permutations,
vector<int> &permutation,
int index) {
const int n = permutation.size();
if (index == n) {
permutations.emplace_back(permutation);
} else {
for (int i = index; i < n; ++i) {
swap(permutation[i], permutation[index]);
search_permutations(permutations, permutation, index + 1);
swap(permutation[i], permutation[index]);
}
}
}
};
Permutation
n = nums.size()
Time complexity: O(nn!)
Space complexity: O(n)
class Solution {
public:
vector<vector<int>> permute(const vector<int> &nums) {
const int n = nums.size();
int count = 1;
for (int i = n; i > 0; --i) {
count *= i;
}
vector<vector<int>> combinations;
combinations.reserve(count);
combinations.push_back(nums);
for (int i = 1; i < count; ++i) {
combinations.emplace_back(next_permutation(combinations[i - 1]));
}
return combinations;
}
private:
vector<int> next_permutation(vector<int> nums) {
const int n = nums.size();
int last_inc_index = n - 1;
while (last_inc_index > 0 && nums[last_inc_index] < nums[last_inc_index - 1]) {
--last_inc_index;
}
if (last_inc_index == 0) {
reverse(nums.begin(), nums.end());
return nums;
} else {
int target = nums[last_inc_index - 1];
reverse(nums.begin() + last_inc_index, nums.end());
int min_valid_index =
upper_bound(nums.begin() + last_inc_index, nums.end(), target) - nums.begin();
swap(nums[min_valid_index], nums[last_inc_index - 1]);
return nums;
}
}
};