LeetCode 46 & 47. Permutations I&II
原创
LeetCode 46 & 47. Permutations I&II
原创
本文讲述的是有关于排列问题，这也是算法中的一个重要的方法：回溯法。
46. Permutations
Given a collection of distinct integers, return all possible permutations.
Example:
Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]题目大意：给出一个数组，这个数组是没有重复数字的，求出这个数组的全排列。
解法：
思路：这个其实就是一个树形问题。树形问题采用回溯法是较为经典的方法。
List<List<Integer>> res = new ArrayList<>();
boolean[] used;
public List<List<Integer>> permute(int[] nums) {
if (nums == null || nums.length == 0) return res;
LinkedList<Integer> p = new LinkedList<>();
used = new boolean[nums.length];
permuteHelper(nums,0,p);
return res;
}
public void permuteHelper(int[] nums,int index,LinkedList<Integer> list){
if (nums.length == index) {
LinkedList<Integer> listClone = (LinkedList<Integer>)list.clone();
res.add(listClone);
return;
}
for (int i = 0 ;i< nums.length;i++){
if(used[i] == false){
list.addLast(nums[i]);
used[i] = true;
permuteHelper(nums,index+1,list);
used[i] = false;
list.removeLast();
}
}
}我个人是不喜欢采用全局变量的，所以还是该为了函数变量。代码如下：
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> permuteRes = new ArrayList<>();
boolean[] used = new boolean[nums.length];
if (nums == null || nums.length == 0) return permuteRes;
LinkedList<Integer> p = new LinkedList<>();
permuteHelper(nums,p,permuteRes,used);
return permuteRes;
}
public void permuteHelper(int[] nums,LinkedList<Integer> list, List<List<Integer>> permuteRes, boolean[] used){
if (nums.length == list.size()) {
LinkedList<Integer> listClone = (LinkedList<Integer>)list.clone();
permuteRes.add(listClone);
return;
}
for (int i = 0 ;i<nums.length;i++){
if(used[i] == false){
list.addLast(nums[i]);
used[i] = true;
permuteHelper(nums,list,permuteRes,used);
used[i] = false;
list.removeLast();
}
}
}这是一个最为基本的排列问题，下面我们来看看一个有重复数字的数组，看看是如何让进行排列的。
List<List<Integer>> res = new ArrayList<>();
boolean[] used; //采用的是全局变量，记录当前的元素是否已经使用了
public List<List<Integer>> permute(int[] nums) {
used = new boolean[nums.length]; // 注意，虽然 used是定义的类的成员变量，但是分配空间可以在子函数里面进行
if (nums.length == 0||nums == null) return res; //如果数组为空或者数组里面没有元素 返回res
LinkedList<Integer> p = new LinkedList<>(); //这里定义为LinkedList的目的是在结尾进行增删操作。
// 如果是ArrayList的话，只能在结尾添加，不能在结尾删除
permute_recursion( nums,0,p); // 初始时候。index的值为0,
return res;
}
/**
*
* @param nums
* @param index
* @param list
*/
public void permute_recursion(int[] nums, int index, LinkedList<Integer> list ) {
if (nums.length == index) { //当前的索引已经超出了 数组的最大的索引 ，说明list中存储的数据已经是一个完整的组合了
LinkedList<Integer> list_clone = (LinkedList<Integer>)list.clone();//java参数是引用专递机制，发现list中存储的是一个完整的组合后，
//将这个组合 克隆一份 添加到res中，否则后续的程序会修改list
res.add(list_clone); //将克隆后的组合添加到res中
return;
}
for (int i =0;i <nums.length ;i++){
if (used[i] == false ){ //这里采用的是一个boolean的数组，来记录当前的索引的元素是否已经使用过
list.addLast(nums[i]); //将新的元素添加到list的尾部，
used[i] = true; // 同时将used的数组 设置为true 表示这个元素已经使用过了
permute_recursion(nums,index+1,list); // 递归
used[i] = false; //清除这个used的标记
list.removeLast(); // 递归完毕后，将最后一个数据删除，以便于尝试其他的组合，这一步也就是回溯算法的“回溯”的体现所在
}
}
}47. Permutations II
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
Example:
Input: [1,1,2]
Output:
[
[1,1,2],
[1,2,1],
[2,1,1]
]解法一：
思路：有重复数字的排列的结果与没有重复数字的排列结果相比较，就是把没有重复数字的排列结果中相同的去掉了。所以我们可以很容易的想到借用java的Set数据结构，可以很容易的排重。
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> permuteRes = new ArrayList<>();
Set<LinkedList<Integer>> set = new HashSet<>();
boolean[] used = new boolean[nums.length];;
if (nums == null || nums.length == 0) return permuteRes;
LinkedList<Integer> p = new LinkedList<>();
permuteHelper(nums,p,set,used);
return new ArrayList<>(set);
}
public void permuteHelper(int[] nums,LinkedList<Integer> list, Set<LinkedList<Integer>> set, boolean[] used){
if (nums.length == list.size()) {
LinkedList<Integer> listClone = (LinkedList<Integer>)list.clone();
set.add(listClone);
return;
}
for (int i = 0 ;i< nums.length;i++){
if(used[i] == false){
list.addLast(nums[i]);
used[i] = true;
permuteHelper(nums,list,set,used);
used[i] = false;
list.removeLast();
}
}
}解法二：
思路：能不能在查找的过程中就排除重复的情况呢？若果能，那么怎么排除呢？重复的情况又是怎样的呢？带着这些问题，我们发现重复的情况是：拿题目中[1,1,2]来说，如果第一次选1(0),第二次选择1(1)，与第一次选1(1),第二次选择1(0)，这是同样的结果，这就是重复的原因，所以当索引为i的数字等于索引为i-1的数字时候，如果索引为i-1的数字没有被使用，那么这种情况就是重复的，应该跳过，转化为程序就是：nums[i]== nums[i-1]&&used[i-1]==false，同时要要考虑此时i>0;所以这个时候，for循环中的判断就是if(used[i]||(i>0&&nums[i]== nums[i-1]&&used[i-1]==false))，满足条件则跳过。
public List<List<Integer>> permuteUnique(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> permuteRes = new ArrayList<>();
boolean[] used = new boolean[nums.length];
if (nums == null || nums.length == 0) return permuteRes;
permuteHelper(nums,new LinkedList<>(),permuteRes,used);
return permuteRes;
}
public void permuteHelper(int[] nums,LinkedList<Integer> list, List<List<Integer>> permuteRes, boolean[] used){
if (nums.length == list.size()) {
LinkedList<Integer> listClone = (LinkedList<Integer>)list.clone();
permuteRes.add(listClone);
return;
}
for (int i = 0 ;i< nums.length;i++){
if(used[i]||(i>0&&nums[i] == nums[i-1]&&used[i-1]==false)) continue;
list.addLast(nums[i]);
used[i] = true;
permuteHelper(nums,list,permuteRes,used);
used[i] = false;
list.removeLast();
}
}
还要注意的是，这样的解法必须数组数有序的数组，由于LeetCode46中的数组是没有重复数字的，因此不需要有序，所以首先要将数组进行一个排序处理。另外：解法二在查找的过程中就已经排除了重复的值，解法一是将左右的找到放在一个Set中进行去重，这样的时间效率显然没有解法二高。这种解法与解法一的不同之处在于，本解法是在查找到过程中就将不符合要求的情况排除出去，因此算法的效率有很明显的提升。
总结：
对与排列组合问题，首先想到的是采用回溯算法，回溯算法是算法中的几个较为经典的算法之一，这个算法的核心思想就是回溯的过程，代码中的list.removeLast();
很多人认为回溯和递归是一样的，其实不然。在回溯法中可以看到有递归的身影，但是两者是有区别的。回溯法从问题本身出发，寻找可能实现的所有情况。和穷举法的思想相近，不同在于穷举法是将所有的情况都列举出来以后再一一筛选，而回溯法在列举过程如果发现当前情况根本不可能存在，就停止后续的所有工作，返回上一步进行新的尝试。递归是从问题的结果出发，例如求 n！，要想知道 n！的结果，就需要知道 n*(n-1)! 的结果，而要想知道 (n-1)! 结果，就需要提前知道 (n-1)*(n-2)!。这样不断地向自己提问，不断地调用自己的思想就是递归。回溯和递归唯一的联系就是，回溯法可以用递归思想实现。
本算法就是回溯的体现，有关组合的问题可以参照《leetCode 77&39. Combinations & Combination Sum》；
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
腾讯云开发者
