46. Permutations
給定一個由不同整數組成的數組 nums，返回所有可能的排列。你可以以任意順序返回答案。
範例 1：
輸入：nums = [1,2,3] 輸出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Python
from typing import List
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
def backtrack(start=0):
# If we have a complete permutation, add it to the results
if start == len(nums):
result.append(nums[:])
return
for i in range(start, len(nums)):
# Swap the current element with the start element
nums[start], nums[i] = nums[i], nums[start]
# Continue generating permutations with the next element
backtrack(start + 1)
# Swap back to backtrack
nums[start], nums[i] = nums[i], nums[start]
result = []
backtrack()
return result
16.76MB, 52ms
C++
#include <vector>
using namespace std;
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> result;
backtrack(nums, 0, result);
return result;
}
private:
void backtrack(vector<int>& nums, int start, vector<vector<int>>& result) {
if (start == nums.size()) {
result.push_back(nums);
return;
}
for (int i = start; i < nums.size(); ++i) {
swap(nums[start], nums[i]);
backtrack(nums, start + 1, result);
swap(nums[start], nums[i]);
}
}
};
8.78MB, 5ms
Javascript
/**
* @param {number[]} nums
* @return {number[][]}
*/
var permute = function(nums) {
const result = [];
const backtrack = (start = 0) => {
if (start === nums.length) {
result.push([...nums]);
return;
}
for (let i = start; i < nums.length; i++) {
// Swap the current element with the start element
[nums[start], nums[i]] = [nums[i], nums[start]];
// Continue generating permutations with the next element
backtrack(start + 1);
// Swap back to backtrack
[nums[start], nums[i]] = [nums[i], nums[start]];
}
};
backtrack();
return result;
};
53.52MB, 75ms
