算法
枚举每个数放哪个位置上
以1,2,3为例:
[ , , ]
/ | \
/ | \
/ | \
[1, , ] [ ,1, ] [ , ,1]
/ \ / \ / \
[1,2, ] [1, ,2] [2,1, ] [ ,1,2] [2, ,1] [ ,2,1]
| | | | | |
[1,2,3] [1,3,2] [2,1,3] [3,1,2] [2,3,1] [3,2,1]
时间复杂度: O(n^n)
空间复杂度: O(n)
C++代码
class Solution {
public:
static vector<vector<int>> permute(const vector<int> &nums) {
vector<vector<int>> res;
if (nums.empty()) {
return res;
}
const int n = static_cast<int>(nums.size());
vector<int> path(n);
vector<bool> pathIndexVisited(n);
permuteDfs(nums, 0, path, pathIndexVisited, res);
return res;
}
private:
static void permuteDfs(const vector<int> &nums, const int numIndex, //
vector<int> &path, vector<bool> &pathIndexVisited, vector<vector<int>> &res) {
const int n = static_cast<int>(nums.size());
if (numIndex == n) {
res.push_back(path);
return;
}
for (int pathIndex = 0; pathIndex < n; ++pathIndex) {
if (!pathIndexVisited[pathIndex]) {
pathIndexVisited[pathIndex] = true;
path[pathIndex] = nums[numIndex];
permuteDfs(nums, numIndex + 1, path, pathIndexVisited, res);
pathIndexVisited[pathIndex] = false;
}
}
}
};
Java代码
class Solution {
public static List<List<Integer>> permute(final int[] nums) {
final List<List<Integer>> res = new ArrayList<>();
if (nums.length == 0) {
return res;
}
final int[] path = new int[nums.length];
final boolean[] pathIndexVisited = new boolean[nums.length];
permuteDfs(nums, 0, path, pathIndexVisited, res);
return res;
}
private static void permuteDfs(final int[] nums, final int numIndex, //
final int[] path, final boolean[] pathIndexVisited, final List<List<Integer>> res) {
if (numIndex == nums.length) {
final List<Integer> pathList = new ArrayList<>(path.length);
for (final int num : path) {
pathList.add(num);
}
res.add(pathList);
return;
}
for (int pathIndex = 0; pathIndex < path.length; ++pathIndex) {
if (!pathIndexVisited[pathIndex]) {
pathIndexVisited[pathIndex] = true;
path[pathIndex] = nums[numIndex];
permuteDfs(nums, numIndex + 1, path, pathIndexVisited, res);
pathIndexVisited[pathIndex] = false;
}
}
}
}
Python3代码
class Solution:
def permute(self, nums: list) -> list:
res = []
if not nums:
return res
n = len(nums)
path = [0] * n
pathIndexVisited = [False] * n
self.__permuteDfs(nums, 0, path, pathIndexVisited, res)
return res
def __permuteDfs(self, nums: list, numIndex: int, #
path: list, pathIndexVisited: list, res: list) -> None:
n = len(nums)
if numIndex == n:
res.append(path.copy())
return
for pathIndex in range(n):
if not pathIndexVisited[pathIndex]:
pathIndexVisited[pathIndex] = True
path[pathIndex] = nums[numIndex]
self.__permuteDfs(nums, numIndex + 1, path, pathIndexVisited, res)
pathIndexVisited[pathIndex] = False
Go代码
func permute(nums []int) [][]int {
res := [][]int{}
n := len(nums)
if n == 0 {
return res
}
path := make([]int, n)
pathIndexVisited := make([]bool, n)
permuteDfs(nums, 0, path, pathIndexVisited, &res)
return res
}
func permuteDfs(nums []int, numIndex int,
path []int, pathIndexVisited []bool, res *[][]int) {
n := len(nums)
if numIndex == n {
tmpPath := make([]int, n)
copy(tmpPath, path)
*res = append(*res, tmpPath)
return
}
for pathIndex := 0; pathIndex < n; pathIndex++ {
if !pathIndexVisited[pathIndex] {
pathIndexVisited[pathIndex] = true
path[pathIndex] = nums[numIndex]
permuteDfs(nums, numIndex+1, path, pathIndexVisited, res)
pathIndexVisited[pathIndex] = false
}
}
}