import java.util.*; public class Solution { private static ArrayList<ArrayList<Integer>> result = new ArrayList<>(); public ArrayList<ArrayList<Integer>> permute(int[] num) { //注意回溯法的通用解法 //引入队列 Deque<Integer> deque = new ArrayDeque<>(); if( num.length == 0){ return result; } //辅助数组,标识是否使用过 boolean[] used = new boolean[num.length]; backTracking(num,deque,used); return result; } public static void backTracking(int[] num,Deque<Integer> list,boolean[] used){ if(list.size() == num.length){ result.add(new ArrayList<>(list)); return; } //注意全排列这里的起点是0,但是组合是startIndex for(int i=0;i<num.length;i++){ if(used[i] == true){ continue; } used[i] = true; list.addLast(num[i]); backTracking(num,list,used); //回溯 used[i] = false; list.removeLast(); } } }
解题思想:dfs标准套路,回朔逐个枚举,主要是确认需要枚举的下一个元素。