循环递归,回溯
class Solution {
List<List<Integer>> res = new LinkedList<List<Integer>>();
boolean[] used = new boolean[1024];// nums中第i个元素是否使用过,添加到path中
public List<List<Integer>> permutation(int[] nums) {
res.clear();
if (nums.length == 0) {
return res;
}
Arrays.sort(nums);
generatePermutation(nums, 0, new LinkedList<>());
return res;
}
// path保存了一个有index个元素的排列
// 向这个排列的末尾添加第index+1个元素,获得一个有index+1个元素的排列
private void generatePermutation(int[] nums, int index, List<Integer> path) {
// boolean[] used = new boolean[nums.length];// nums中第i个元素是否使用过,添加到path中
if (index == nums.length) {
res.add(new ArrayList<Integer>(path));
return;
}
// 循环加递归!!就是回溯!!
for (int i = 0; i < nums.length; i++) {
if (used[i] || i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
continue;
}
path.add(nums[i]);
used[i] = true;
// 尝试着将所有剩余没有用过的元素添加到path中去,将所有没有用过的元素,添加到index位置
// 可以这样理解,在循环中,只有i是变化的,index是不变的,因此就可以看作是将所有的元素遍历一遍,尝试添加到index位置上
generatePermutation(nums, index + 1, path);
// 回复状态,添加循环后的另一个元素,将循环遍历的所有元素都尝试添加一遍,回溯
path.remove(index);
used[i] = false;
}
}
}