官方链接
https://leetcode-cn.com/problems/permutations/
给定一个没有重复数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]视频资源
https://www.youtube.com/watch?v=oCGMwvKUQ_I
解法一
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
self.res = []
self.dfs(nums, [])
return self.res
def dfs(self, nums: List[int], temp):
if len(temp) == len(nums):
self.res.append(temp[:])
for i in range(len(nums)):
if nums[i] in temp:
continue
temp.append(nums[i])
self.dfs(nums, temp)
temp.pop()
用时有点长，空了优化
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
dfs(result, nums, nums.length, new ArrayList<>());
return result;
}
private void dfs(List<List<Integer>> result, int[] nums, int n, List<Integer> res) {
// terminator
if (nums.length == 0 && res.size() == n) {
result.add(new ArrayList<>(res));
return;
}
// process
// drill down
for (int i = 0; i < nums.length; i++) {
int [] nums1 = new int[nums.length - 1];
System.arraycopy(nums, 0, nums1, 0, i);
System.arraycopy(nums, i + 1, nums1, i, nums.length - i - 1);
dfs(result, nums1, n, res);
res.add(nums[i]);
dfs(result, nums1, n, res);
res.remove(res.size() - 1);
}
// reverse
}
}