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(const vector<int> &nums) {
vector<int> permutation(nums);
_search_permutations(permutation, 0);
return _full_permutations;
}
private:
vector<vector<int>> _full_permutations;
void _search_permutations(vector<int> &permutation, int index) {
if (index == permutation.size()) {
_full_permutations.emplace_back(permutation);
} else {
for (int i = index; i < permutation.size(); ++i) {
swap(permutation[i], permutation[index]);
_search_permutations(permutation, index + 1);
swap(permutation[i], permutation[index]);
}
}
}
};