package LeetCode;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class LeetCode47 {
//https://leetcode-cn.com/problems/permutations/description/
// 全排列
private ArrayList> res;
private boolean[] used;
public List> permute(int[] nums) {
res = new ArrayList<>();
if (nums == null || nums.length == 0)
return res;
used = new boolean[nums.length];
LinkedList p = new LinkedList<>();
generatePermutation(nums, 0, p);
return res;
}
// pä¸ä¿å˜äº†ä¸€ä¸ªæœ‰index-1ä¸ªå…ƒç´ çš„æŽ’åˆ—ã€‚
// å‘è¿™ä¸ªæŽ’åˆ—çš„æœ«å°¾æ·»åŠ ç¬¬indexä¸ªå…ƒç´ , 获得一个有indexä¸ªå…ƒç´ çš„æŽ’åˆ—
private void generatePermutation(int[] nums, int index, LinkedList p) {
if (index == nums.length) {
res.add((List) p.clone());
return;
}
for (int i = 0; i < nums.length; i++)
if (!used[i]) {
used[i] = true;
p.addLast(nums[i]);
generatePermutation(nums, index + 1, p);
// 回溯完è¦æ¸…除状æ€
p.removeLast();
used[i] = false;
}
return;
}
private static void printList(List list) {
for (Integer e : list)
System.out.print(e + " ");
System.out.println();
}
public static void main(String[] args) {
int[] nums = {1, 2, 3};
List> res = (new LeetCode47()).permute(nums);
for (List list : res)
printList(list);
}
}