全排列

package 全排列; import java.util.*; /** * 回溯+深度优先遍历 */ class Solution { public static void main(String[] args) { // int数组全排列调用 List<List<Integer>> result = permute(new int[]{1,2,3}); System.out.println(result); // 字符串全排列调用 Set<String> result2 = new HashSet<>(); permutation("abcd".toCharArray(), 0, 3, result2); System.out.println(result2); } // 1、int数组全排列 public static List<List<Integer>> permute(int[] nums) { int len = nums.length; List<List<Integer>> res = new ArrayList<>(); if(len == 0) return res; Stack<Integer> path = new Stack<>(); boolean used[] = new boolean[len]; dfs(nums,len,0,path,used,res); return res; } private static void dfs(int[] nums, int len, int depth, Stack<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]) continue; //将该元素添加到栈顶 path.push(nums[i]); used[i] = true; dfs(nums,len,depth+1,path,used,res); //回溯 path.pop(); used[i] = false; } } // 2、字符串全排列 private static void permutation(char[] a, int from, int to, Set<String> result) { if(a== null || from>to || from<0) { return; } if(from == to) { result.add(String.valueOf(a)); } for(int i = from; i <= to; i++) { swap(a,i,from); permutation(a, from +1,to, result); swap(a,i,from); } } private static void swap(char[]a, int left, int right) { char temp = a[left]; a[left] = a[right]; a[right] = temp; } }