import java.util.ArrayList;

import java.util.Collections;

import java.util.List;

public class Permute_46 {

private int n;

public List<List<Integer>> permute(int[] nums) {

n = nums.length;

List<List<Integer>> res = new ArrayList<>();

if (nums == null || n == 0) {

return res;

}

List<Integer> path = new ArrayList<>();

for (int num : nums) {

path.add(num);

}

backtrack(0, path, res);

return res;

}

private void backtrack(int first, List<Integer> path, List<List<Integer>> res) {

if (first == n) {

// 这里陷阱不能直接add(path)，path为引用型变量实际存的list就始终变成了一个

// res.add(path);

res.add(new ArrayList<Integer>(path));

return;

}

for (int i = first; i < n; i++) {

Collections.swap(path, first, i);

backtrack(first + 1, path, res);

Collections.swap(path, first, i);

}

}

}