排列

算法思路：

Leetcode 046的题目。这里作为知识点归纳。

1. 类似于组合题，但用到了visited数组且递归中从i=0开始。

应用：

1. 找所有可能性

注意事项：

1. 每一种排列加入到结果集时要复制path。

Leetcode 046 Permutations

def permute(self, nums: List[int]) -> List[List[int]]:
	if not nums:
		return [[]]
	path, result, visited = [], [], set()
	self.dfs(nums, path, result, visited)
	return result

def dfs(self, nums, path, result, visited):
	if len(path) == len(nums):
		result.append(list(path))
		return

	for i in range(len(nums)):
		if i in visited:
			continue
		path.append(nums[i])
		visited.add(i)
		self.dfs(nums, path, result, visited)
		visited.remove(i)
		path.pop()

Java代码：

public List<List<Integer>> permute(int[] nums) {
	List<Integer> path = new ArrayList<>();
	List<List<Integer>> res = new ArrayList<>();
	if(nums == null) {
		return res;
	}
	dfs(nums, new HashSet<>(), path, res);
	return res;
}

void dfs(int[] nums, Set<Integer> visited, List<Integer> path, List<List<Integer>> res) {
	if(path.size() == nums.length) {
		res.add(new ArrayList<>(path));
		return;
	}
	
	for(int i = 0; i < nums.length; i++) {
		if(visited.contains(i))
			continue;
		visited.add(i);
		path.add(nums[i]);
		dfs(nums, visited, path, res);
		visited.remove(i);
		path.remove(path.size() - 1);
	}
}

算法分析：

时间复杂度为O(n!)，空间复杂度O(1)。