1
package 回溯法.q46_全排列.f1;
import java.util.ArrayList;
import java.util.List;
/**
* 插队法 o((n-1)!+(n-2)!+···+2!+1!)
*/
public class Solution {
public List<List<Integer>> fc(List<List<Integer>> nums, int c) {
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < nums.size(); i++) {
for (int j = 0; j <= nums.get(i).size(); j++) {
List<Integer> temp = new ArrayList<>(nums.get(i));
temp.add(j, c);
result.add(temp);
}
}
return result;
}
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
if (nums.length == 0) {
return result;
}
List<Integer> to = new ArrayList<>();
to.add(nums[0]);
result.add(to);
for (int i = 1; i < nums.length; i++) {
result = fc(result, nums[i]);
}
System.out.println(result);
return result;
}
public static void main(String[] args) {
new Solution().permute(new int[]{1, 2, 3});
//4—>3！+2！+1！
}
}
2
package 回溯法.q46_全排列.f2;
import java.util.ArrayList;
import java.util.List;
/**
* 回溯法(DFS深度优先遍历) o(n*n!)
*/
public class Solution {
public List<List<Integer>> permute(int[] nums) {
int len = nums.length;
List<List<Integer>> res = new ArrayList<>();
if (len == 0) {
return res;
}
boolean[] used = new boolean[len];
List<Integer> path = new ArrayList<>();
dfs(nums, len, 0, path, used, res);
return res;
}
private void dfs(int[] nums, int len, int depth,
List<Integer> path, boolean[] used,
List<List<Integer>> res) {
if (depth == len) {
res.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < len; i++) {
if (!used[i]) {
path.add(nums[i]);
used[i] = true;
dfs(nums, len, depth + 1, path, used, res);
// 状态重置，是从深层结点回到浅层结点的过程，代码在形式上和递归之前是对称的
used[i] = false;
path.remove(depth);
}
}
}
public static void main(String[] args) {
int[] nums = {1, 2, 3};
Solution solution = new Solution();
List<List<Integer>> lists = solution.permute(nums);
}
}