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