LC-46：全排列（不包含重复元素）
LC-46：全排列
我的实现思路：
该算法是一个对给定序列进行全排列的算法，所以需要对该序列进行递归查询所有的可能出现的序列，比如：[1,2,3] 可能就会出现[1,2,3] , [1,3,2] , [2,1,3] , [2,3,1] , [3,1,2] , [3,2,1]，具体是这样分析的，如下图：
在图中会发现一个问题，对于每一个元素的每一种情况都包含在内，但是里面肯定是有重复的序列的，这个时候，完全可以使用Set集合对立面出现的所有的序列进行去重，最终保存剩余的序列，但是为了考虑时间复杂度和空间复杂度的问题，所以这种情况不做考虑。
如何改进呢？
使用回溯法：所谓额回溯法，就是他会对你所有的情况进行遍历，当没有或者说没有符合情况的条件的时候，就会进行回退，实现部分还原，以便对其他的分值进行遍历，在这里我使用的是最经典的visited标志实现对每一个元素的判断。用visited对里面出现的元素设置为true，还没有出现的设置为false，回退时，将已出现的元素标志设置为false。
算法的思路步骤：
第一步：创建一个ArrayList的数组，泛型是一个List<Integer>用于在ArrayList数组中再次存多个数组；
第二步：创建一个visited标志，对原始的数组里面的原有的元素，都保存hashmap中，默认都设置为false；
第三步：声明一个函数，将原始数组、visited、ArrayList最终的结果保存集、再创建一个新的ArrayList用于保存每一个新的完全的序列；
第四步：对该函数进行具体实现，该函数是一个递归函数，首先，实现递归的结束体，只有当新的序列的长度等于数组的长度的时候，就说明，将所有的元素的情况进行遍历完毕，然后将该序列保存在最终的结果集中；接下来就是判断，数组中的每一个元素，for循环，if判断该元素是否没有被遍历过，若没有遍历过，就执行向list序列添加，状态改为true，然后再次执行递归函数，进行深度递归，当递归完成时，是需要进行回溯的，所以进行状态的重新改变，list长度减一。
我的实现代码：
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
HashMap<Integer,Boolean> visited = new HashMap<>();
for (int number : nums) {
visited.put(number,false);
}
backtracking(nums,result,visited,new ArrayList<Integer>());
return result;
}
public void backtracking(int[] nums,List<List<Integer>> result,HashMap<Integer,Boolean> visited,ArrayList<Integer> list) {
if (nums.length == list.size()) {
result.add(new ArrayList<Integer>(list));
return;
}
for (int i = 0; i < nums.length; i++) {
int temp = nums[i];
if (!visited.get(temp)) {
list.add(temp);
visited.put(temp,true);
backtracking(nums,result,visited,list);
list.remove(list.size() - 1);
visited.put(temp,false);
}
}
}
}
投递小米集团等公司10个岗位
