企业官网建设流程全解析

直觉就是递归+回溯。

思路：比如输入是{1,2,3,4}，就是{1,2,3,4}里任意一个元素+剩下所有元素全排列。就是1+{2,3,4}的全排列，2+{1,3,4}的全排列，3+{1,2,4}的全排列，4+{1,2,3}的全排列。
step01: 定义递归问题dps(int nums[])为：nums[]里所有元素的全排列
step02：语义其实在一开始思考思路的时候已经写出来了
step03: dps(int nums[]) = for(int i=0; i<nums.length;i++){

i+dps(nums[i]之外的其他元素)

}
再就是需要回溯，这个很好判断，在《递归篇》里讲过是否需要回溯的判断。

因为每次进入子递归都要去掉当前递归用到的元素nums[i]，我本来想的是用set.remove的方式。

致命的错误在于，集合在for循环里不能remove。这里就用到了标记数组int[] used，used[i]=0标记为没用过，used[i]标记为用过。

class Solution { public List<List<Integer>> permute(int[] nums) { int[] used=new int[nums.length]; //构造递归参数 List<List<Integer>> result = new ArrayList<>(); //构造递归参数 List<Integer> temp = new ArrayList<>(); //构造递归参数 dps(nums,used,temp,result); return result; } public void dps(int[] nums, int[] used, List<Integer> temp, List<List<Integer>> result){ //递归出口 if(temp.size()==nums.length){ result.add(new ArrayList<>(temp)); //坑，别写成result.add(temp);这样的话结果全是[[][][][]] return; } //递推关系 for(int i=0;i<nums.length;i++){ if(used[i]==0){ used[i]=1; //引用传递，只能写成穿脱原则 temp.add(nums[i]); //引用传递，只能写成穿脱原则 dps(nums,used,temp,result); temp.remove(temp.size()-1); used[i]=0; } } } }

还有一点要注意的是，递归出口那里，因为temp是引用传递，所以要把他的值拷贝一下重新new一个对象再放进result里，如果写成result.add(temp)的话，最后得到的是一片空集合。