算法通关村第十八关——排列问题

LeetCode46.给定一个没有重复数字的序列，返回其所有可能的全排列。例如：

输入：[1,2,3]
输出：[[1,2,3]，[1,3,2]，[2,1,3]，[2,3,1]，[3,1,2]，[3,2,1]]

元素1在[1,2]中已经使用过了，但是在[2,1]中还要再使用一次，所以就不能使用startlndex了，为此可以使用一个used数组来标记已经选择的元素

class Permute {List<List<Integer>> res = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();boolean[] used;public List<List<Integer>> permute(int[] nums) {if (nums.length == 0) {return res;}used = new boolean[nums.length];permuteHelper(nums);return res;}private void permuteHelper(int[] nums) {if (path.size() == nums.length) {res.add(new ArrayList<>(path));return;}for (int i = 0; i < nums.length; i++) {if (used[i]) {continue;}used[i] = true;path.add(nums[i]);permuteHelper(nums);path.removeLast();used[i] = false;}}
}

在这里for循环中，used[i]的变化可以这样理解，现在这一层刚上来当前元素肯定是没有使用过的，在执行了将used数组当前元素变为已使用，将当前元素添加到path中后，就要进入他的下一层了，在他的下面几层当前元素都是使用过的。