一、回溯法【路径，选择条件，结束条件】
回溯法，其实也是决策树，核心代码，就是for循环里面的递归，在递归调用之前【做出选择】，递归调用之后【撤销选择】
# 核心代码 result = [] def backtrack(路径，选择列表): if 满足条件： result.add(路径) return for 选择 in 选择列表： 做选择 backtrack(路径，选择列表) 撤销选择
完整代码：
public class Permute { List<List<Integer>> res = new ArrayList<List<Integer>>(); public List<List<Integer>> permute(int[] nums) { if (nums == null || nums.length ==0) return res; helper(nums,new ArrayList<Integer>()); return res; } private void helper(int[] nums, ArrayList<Integer> tmp) { if (tmp.size() == nums.length){ res.add(new ArrayList<>(tmp)); return; } for (int i = 0; i < nums.length; i++) { if (tmp.contains(nums[i])) continue; tmp.add(nums[i]); helper(nums,tmp); tmp.remove(tmp.size()-1); } } }
二、另辟蹊径新方法【搞怪的方法，很简单实用】
有时候，我觉得暴力一点也很好，但是我看到很多暴力的代码，需要比较交换很多次，严重的影响的代码的阅读，我想出了一个直接利用最大值循环，并利用Collections.shuffle的方法，因为最后的全排序的值时固定的，利用一个set集合，当达到了这个之后，直接退出循环就好。
你想到这个思想的小问题在哪里吗？
问题：只能计算输出没有重复元素的数组
public static void permute2(int[] nums) { if (nums == null || nums.length == 0) { //return new ArrayList<>(); } // 共有多少种情况 int sum = 1; for (int i = nums.length; i>0; i--) { sum = sum * i; } System.out.println(sum); ArrayList<Integer> list = new ArrayList<>(); for (int num : nums) { list.add(num); } Set<List<Integer>> set = new HashSet<>(); for (int i = 0; i < 3000000; i++) { Collections.shuffle(list); ArrayList<Integer> templist = new ArrayList<>(list); set.add(templist); // set集合的大小 = 指定的数量 退出循环 if (set.size() == sum){ break; } System.out.println(i); } System.out.println(set); }
执行结果：最终执行了10次就退出循环了 【每次执行总次数不一样】
