PermutationII [source code]
public class PermutationII {
static
/******************************************************************************/
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> res_lss = new ArrayList <> ();
Arrays.sort (nums);
boolean[] used = new boolean[nums.length];
dfs (nums, res_lss, new ArrayDeque<> (), used);
return res_lss;
}
void dfs (int[] nums, List<List<Integer>> lss, Deque<Integer> path, boolean[] used) {
String header;
if (path.size () == nums.length) {
lss.add (new ArrayList<> (path));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i])
continue;
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])
continue;
used[i] = true;
path.push (nums[i]);
dfs (nums, lss, path, used);
used[i] = false;
path.pop ();
}
}
String array (int[] nums) {
return Arrays.deepToString (new int[][] {nums});
}
String wrap (String s, int code) {
return (char) 27 + "[" + code + "m" + s + (char) 27 + "[0m";
}
}
/******************************************************************************/
public static void main(String[] args) {
PermutationII.Solution tester = new PermutationII.Solution();
int[][] inputs = {
{1,1,2},
{2,1,1},
};
int[][][] answers = {
{
{1,1,2},
{1,2,1},
{2,1,1},
},
{
{1,1,2},
{1,2,1},
{2,1,1},
},
};
for (int i = 0; i < inputs.length; i++) {
int[] nums = inputs[i];
int[][] ans = answers[i];
System.out.println (Printer.separator ());
List<List<Integer>> output = tester.permuteUnique (nums);
System.out.printf ("[%s] -> %s, expected: \n%s\n",
Printer.array (nums), output.toString ().replaceAll ("],", "],\n"), Matrix.printMatrix (ans)
);
}
}
}
duplicate的处理看来是这一题的难点; 因为这题看来最主要的难点就是去重, 所以直接用set的方法在实际的面试当中肯定不会过关;
permutation问题自然而然的用size-based的方法更加有利; 那么我们之前做combination sum的时候, size based的时候的去重是怎么完成的?
暂时没有看到什么思路, 问题启发, 直接先考虑, 为什么我们本来的permutation算法不能handle duplicate? 跑一个trace, 看看到底是哪里有问题;
我发现我做题的时候, 现在跟他们科班的一个差距就是, 我太在于任何仅仅一闪而过的思路的正确性; 我往往只是有一点思路的时候, 脑子突然会停顿, 因为潜意识里面担心不对, 所以还有点短暂停顿; 实际上, 他们科班, 一旦有了一个点子, 立刻就开始根据一个粗略的逻辑来跑trace; 如果感觉逻辑太复杂, 就写代码来跑跑看, 这个总比你发呆要强.
计算机科学就是这样一个学科, 你不是先知, 别人动笔动代码才能得到的答案, 你两眼一闭就想冥想出来, 未免是想多了;
一个点子如果是一闪而过, 要么快速证明他是对的, 要么快速证明是错的, 翻篇儿. 不要连跑都不跑就在发呆;
我感觉我还是走歪了, 去重问题的一个重要的思路, 是先思考, 为什么会有重复? 什么样的才算重复? 然后才来重点的针对; 很多时候就是试着试着就找到了正确的思路(或者从错的思路当中得到启发), 之后才想到去怎么证明;
一个简单的想法, 就是每一个position(size based)都记录一个曾经用过的数字, 这样, 假如随机选出来的数字以前已经见过, 那么就不用; 但是感觉这个做法最后好像其实还是依靠set来去重, 不知道是不是合格;
算了, 没思路, 不管了;
最后是参考discussion最优解写出来的, 速度是9ms (39%). 感觉最后还是这个算法能够学习到的东西最多; 这题最后看下来难度比第一题其实是提升很多的, 不过最后见到的思路其实也很多;
没有editorial;
@UpTheHell said in Really easy Java solution, much easier than the solutions with very high vote:
Use an extra boolean array " boolean[] used" to indicate whether the value is added to list.
Sort the array "int[] nums" to make sure we can skip the same value.
when a number has the same value with its previous, we can use this number only if his previous is used
public class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(nums==null || nums.length==0) return res;
boolean[] used = new boolean[nums.length];
List<Integer> list = new ArrayList<Integer>();
Arrays.sort(nums);
dfs(nums, used, list, res);
return res;
}
public void dfs(int[] nums, boolean[] used, List<Integer> list, List<List<Integer>> res){
if(list.size()==nums.length){
res.add(new ArrayList<Integer>(list));
return;
}
for(int i=0;i<nums.length;i++){
if(used[i]) continue;
if(i>0 &&nums[i-1]==nums[i] && !used[i-1]) continue;
used[i]=true;
list.add(nums[i]);
dfs(nums,used,list,res);
used[i]=false;
list.remove(list.size()-1);
}
}
}
自己在思考的时候, 还在纠结什么随机数的问题, 这个明显是进错片场了, 这题要的是all permutation, 根本用不到随机数; 看到这个算法才想起来这一点;
这个算法其实不是很难理解, 就是一个标准的size based, 每一个level对应的是一个position; 但是我为什么最后没有想到这个算法? 因为我脑子里还是定死了我自己之前给permutation写的算法: 那个算法是一直用swap来mutate nums; 所以虽然思考的时候思考到了用类似combination sum II里面的类似的方法来去重, 但是那个方法依赖的一个性质就是sort之后, 而我这个一直swap的做法, 是直接就打乱sort, 所以直接就放弃这条路了;
但是他这里就是避免了mutation, 用一个单独的accum来记录path; base case也很好判断, 完全没有什么好担心的; 其他的地方基本就跟基本的size-based backtracking一样了; 不过我感觉好像他这里这个used的flag不是必要的? 用一个start index来控制每一个position的搜索范围好像也可以?
反正首先你给记住一个, 去重问题, 在用size based的时候, 好像是有这里这个专门的套路的, 见到两次了;
这题因为最后要的是permutation而不是combination, 也就是有order, 我感觉element based的思路好像会麻烦很多;
@Tōsaka-Rin said in Really easy Java solution, much easier than the solutions with very high vote:
@thalaivva
I think bothif(i > 0 && nums[i] == nums[i - 1] && !use[i - 1]) continue;and
if(i > 0 && nums[i] == nums[i - 1] && use[i - 1]) continue;works. It's weird.
I will try to explain it. Suppose during the ith loop, we have two consecutively same numbers, aka nums[i - 1] and nums[i]. If we add nums[i - 1] to the current list during the (i - 1)th loop and add nums[i] during the ith loop, the list will be the unique one in the result. Now lets move on. During the (i -1)th loop, if we ignore nums[i - 1] and add num[i] to the current list, since nums[i - 1] is not added thus used[i - 1] is false, plus nums[i] == nums[i - 1], hence the if-else limitation should be coded like the first one.
But I also did not figure out why the first one also got accepted. Still, hope my explanation can be inspiring.
想了半天没有想通, 自己画了一个trace:
注意我这里的trace的画法, 是类似NLP的画法, 还是让每一个position代表edge, 而不是node! 虽然我们说每一个position对应一个level, 但是因为你每一个position可以选择的太多, 所以画成edge更加的好看出来;
这个结果好像是符合这个人的回复的:
@ruijun3 said in Really easy Java solution, much easier than the solutions with very high vote:
@传说选手
Another explanation for why both1. if(i > 0 && nums[i] == nums[i - 1] && !use[i - 1]) continue;and
2. if(i > 0 && nums[i] == nums[i - 1] && use[i - 1]) continue;work is given below:
The problem for Permutation II is that different orders of duplicates should only be considered as one permutation. In other words, you should make sure that when these duplicates are selected, there has to be one fixed order.
Now take a look at code 1 and 2.
Code 1 makes sure when duplicates are selected, the order is ascending (index from small to large). However, code 2 means the descending order.
在思考的过程当中, 我难免要和之前的那个第一题的那种swap的算法进行比较; 我现在认为, 当时那个swap的做法只是一个更加取巧的, 在当时的条件下可以用的方法, 而这里的老老实实用used flags, 然后不传递start, 每一个level都从头开始扫的, 才是最general的做法; 在第一题的题意下面, 正好可以用start来完成一个used加上path合并的功能: used的都已经在start的左边所以不会被iterate到, 然后左边这些同时成为了path;
回过头来, 为什么这里这个算法可以完成一个去重? 为什么这里不能跟combination sum II那样, 直接一个跳掉重复的就可以了?
首先, 这个是一个permutation问题, 所以我们最后只在leaf的位置terminate, terminate的时候, 所有的, 比如1,2,2,2,3当中2, 都肯定是出现在这个permutation当中的; 他这里的两种写法, 无论是保证升序还是降序, 最后的做法都是, 当你选择要use一个2的时候, 前面的2必须要used/unused. 我们只讨论第一种假如我们走到2b的时候, 要求2a必须已经被used了, 同样的, 要use 2c的时候, 要求2b一定要已经在path里面了(要本质上理解used是什么意思! 其实就是included in path already: 要从tree的角度来理解). 这个最后就导致, 只有abc一个顺序可以被保留下来, 所有的其他的类似bac的, 肯定不可能; 类似的, 第二种写法保证要求必须cba, 虽然实际的trace相对复杂一些;
虽然这个人的标题上面说这个算法很easy, 但是实际上并不是代码看起来那么trivial; 这里这个enforce order的完成并不是那么简单, 谁能想到用这样一个方式来保证order? if use me, must make sure previous also (not) used.
我还是不死心, 然后模仿之前combination sum II的做法写了这个:
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> res_lss = new ArrayList <> ();
Arrays.sort (nums);
dfs (nums, 0, res_lss, new ArrayDeque<> ());
return res_lss;
}
void dfs (int[] nums, int start, List<List<Integer>> lss, Deque<Integer> path) {
String header;
if (path.size () == nums.length) {
lss.add (new ArrayList<> (path));
return;
}
for (int i = start; i < nums.length; i++) {
if (i > start && nums[i] == nums[i - 1]) // i > start, not 0
continue;
path.push (nums[i]);
dfs (nums, i + 1, lss, path);
path.pop ();
}
}
但是这个代码是错的; 根本就不会达到任何一个leaf位置:
nums:[[1, 1, 2]], start:(0), lss:[], path:[]
nums:[[1, 1, 2]], start:(0), lss:[], path:[] >>>
nums:[[1, 1, 2]], start:(1), lss:[], path:[1]
nums:[[1, 1, 2]], start:(1), lss:[], path:[1] >>>
nums:[[1, 1, 2]], start:(2), lss:[], path:[1, 1]
nums:[[1, 1, 2]], start:(2), lss:[], path:[1, 1] >>>
nums:[[1, 1, 2]], start:(3), lss:[], path:[2, 1, 1]
nums:[[1, 1, 2]], start:(3), lss:[], path:[2, 1, 1] >>> HIT
nums:[[1, 1, 2]], start:(1), lss:[], path:[1] >>>
nums:[[1, 1, 2]], start:(3), lss:[[2, 1, 1]], path:[2, 1]
nums:[[1, 1, 2]], start:(0), lss:[], path:[] >>>
nums:[[1, 1, 2]], start:(3), lss:[[2, 1, 1]], path:[2]
我大概理解为什么之前CombinationSumII的时候, 可以用start, 而这里不可以. start的作用是收缩备选的pool; 之前在CombinationSumII问题的时候, 可以这样做是因为, 我们可以选择not pick一些element; 但是在这里不行啊! 这里你是一个permutation, 你所有的element必须全都要pick; 所以如果不动用swap, 你start过掉一个element之后, 后面就没有办法pick他了, 这个不是我们想要的;
这样看来, 也是格外佩服这个OP算法的巧妙性了; 另外, 这个算法是没有什么特别好的declarative的理解方式的, 理解这里的imperative的运作方式, 更加重要一些;
再来看一个错误的解释:
@batorgil said in Really easy Java solution, much easier than the solutions with very high vote:
@Janop
Consider the following example:
i= 0, 1, 2, 3, 4
A= 1, 1, 1, 2, 2In the for loop, at i = 0, we will form permutations of form [1] + permutations({1,1,2,2}).
At i = 1, !used[0] means that we're on to next iteration and we don't need to consider [1] + permutations({1,1,2,2}) again. Similar for at i = 2, !used[1] means that we've already considered similar permutations.However, note that used[0] could be true, and that can happen for a permutations of {1,1,2,2}.
看起来很有道理, 实际上是完全没有理解这个算法的本质; 我们之所以不允许在2a unused的情况下use 2b, 是因为这样最后2b就一定在2a前面了(2a后面是始终会被pick的), 这样就违反了我们的order; 这种太意识流的理解完全没有抓到精髓, 居然也能骗到两个upvote;
@GoCodeZ said in Really easy Java solution, much easier than the solutions with very high vote:
Another option to avoid duplicate num without sorting 'int[] nums' first, is to utilize a HashSet to track what numbers are used before, if we've used that number then skip it
public class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
if(nums != null || nums.length != 0)
permutationHelper(nums, new int[nums.length], new ArrayList<Integer>());
return unique_perms;
}
List<List<Integer>> unique_perms = new ArrayList<List<Integer>>();
void permutationHelper(int[] nums, int[] numsVisited, List<Integer> result){
if(result.size() == nums.length){
unique_perms.add(new ArrayList<Integer>(result));
return;
}
HashSet<Integer> existingNums = new HashSet<Integer>();
for(int i = 0; i < nums.length; i++){
//if this num was visited before then skip
if(numsVisited[i] == 1) continue;
//if we use this num before then skip it.
if(existingNums.contains(nums[i]))
continue;
else
existingNums.add(nums[i]);
result.add(nums[i]);
numsVisited[i] = 1;
permutationHelper(nums, numsVisited, result);
result.remove(result.size()-1);
numsVisited[i] = 0;
}
}
}
这个就是我之前思考的时候, 每一个position维护一个set的思路, 当时只是想了一下这个观点, 但是没有深挖, 以为实现起来麻烦, 但是实际上这个set是一个local变量, 实现起来其实很简单; 如果真正面试的时候, 我觉得这个点子就很不错; 毕竟好想出来很多: 只要理解为什么duplicate会出现(从源头去重), 那么就很自然的能想到这个方法, 这个也比set of path要细腻一些, 真正的面试的时候应该是可以被接纳的; 笨办法好过没办法, 对吧;
下面有评论认为倒序的去重效率更差:
@chenxingyustar said in Really easy Java solution, much easier than the solutions with very high vote:
First of all, the conclusion is both
!use[i - 1]anduse[i - 1]work, but the!use[i - 1]is more efficient.Here goes the explanation:
If we use
if(i > 0 && nums[i] == nums[i - 1] && use[i - 1]) continue;Chances are that we have the same value,and we will never have chance to use the second one, which causes thelistwill never grow to the length ofnums.length, and waste exists.
Here we have an example of the simple [1, 2, 2']. We start at list = [], and in the first level of backtrack, we have:
[1]
[2]
[2']
In the second level, when list = [1], ve:
[1, 2]
[1, 2']
When list = [2], when i = 0 we have [2, 1] without difficulty, when i = 1, "2" is already used so we simply continue. But when i = 2, we found that nums[2] = nums[1] and nums[1] is already used, so we discard it and the list is still [1]. The problem is that when we have to figure out the next element of this track, we will find that the "2'" will never be used becausenums[2] == nums[1] && used(nums[1])is always true. This track will never reach the recursive base and be added to the final answer.If we use
if(i > 0 && nums[i] == nums[i - 1] && !use[i - 1]) continue;When we figure out the first element of the list,when i = 2 we find that
nums[2] == nums[1]true andused(nums[1])false, so we directly skip the list starting with "2'", and we get
[1] and
[2]
only. The same rule continues on the next steps so every list we generated will reach to an end and return.That why
!use[i - 1]is better. Hope that my explanation is clear enough.
没有仔细看, 不过他这个观点提出来, 大概理解这个想法, 回头看一下我之前的trace, 可以看到, 第一种做法, 确实可以在更高的level prune掉一些, 所以最后实际的效率是好一些的; 这个人的表达乱七八糟的, 懒得看了;
@guoang said in A simple C++ solution in only 20 lines:
class Solution {
public:
void recursion(vector<int> num, int i, int j, vector<vector<int> > &res) {
if (i == j-1) {
res.push_back(num);
return;
}
for (int k = i; k < j; k++) {
if (i != k && num[i] == num[k]) continue;
swap(num[i], num[k]);
recursion(num, i+1, j, res);
}
}
vector<vector<int> > permuteUnique(vector<int> &num) {
sort(num.begin(), num.end());
vector<vector<int> >res;
recursion(num, 0, num.size(), res);
return res;
}
};
这个就很邪门了, swap的做法居然是可以的?
[1,2a,2b,2c,3], 0;
k = 0:
[1,2a,2b,2c,3], 1;
k = 1:
[1,2a,2b,2c,3], 2;
k = 2:
[1,2a,2b,2c,3], 3;
k = 3:
[1,2a,2b,2c,3], 4; HIT
k = 4:
[1,2a,2b,3,2c], 4; HIT
k = 3:
[1,2a,2c,2b,3], 3; // skipped
k = 3: // skipped
[1,2a,2c,2b,3], 4; HIT // skipped
k = 4: // skipped
[1,2a,2c,3,2b], 4; HIT // skipped
k = 4:
[1,2a,3,2c,2b], 3;
k = 3:
[1,2a,3,2c,2b], 4; HIT
k = 4:
[1,2a,3,2b,2c], 4; HIT
k = 2:
[2a,1,2b,2c,3], 2;
k = 2:
[2a,1,2b,2c,3], 3;
k = 3:
[2a,1,2b,2c,3], 4; HIT
k = 4
[2a,1,2b,3,2c], 4; HIT
k = 3:continue;
k = 4:
[2a,1,3,2c,2b], 3;
k = 3:
[2a,1,3,2c,2b], 4; HIT
k = 4: continue;
k = 3:
...
我trace算错了吗? 怎么感觉好像是有duplicate的? 但是这个答案确实是AC的; 哦, 忘记去重了;
不对, 上面的trace不对, 你看出来哪里不对了吗? 他这里每一个循环里面只有一个swap, 也就是对于每一个k, 没有undo; 这也是为什么这个算法很难理解的原因; 另外, 虽然像这样type trace是可行的, 但是感觉速度还是太慢了;
另外, 后来看了一下下面的讨论, OP这里的这个做法, 实际上是一个pass by value!!! 所以并不是一个mutation;
底下也有人讨论这个:
@TonyLic said in A simple C++ solution in only 20 lines:
Basically your idea is sorting first and then applying same method for permutation I. Here is my code which is similar except I use reference for num in the helper function, why did I get TLE on [3,3,0,0,2,3,2]. Could anyone give me a hint???
class Solution {
public:
void helper(vector<vector<int>>& res, int pos, vector<int>& nums)//0...pos-1 already permutated
{
if(pos == nums.size())
{
res.push_back(nums);
return;
}
for(int i = pos; i < nums.size(); ++i)
{
if(i != pos && nums[i] == nums[pos]) continue;
swap(nums[i], nums[pos]);
helper(res, pos + 1, nums);
swap(nums[i], nums[pos]);
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> res;
if(nums.empty())return res;
sort(nums.begin(), nums.end());
helper(res, 0, nums);
return res;
}
};
他说的问题是一个方面, 但是实际上这个算法还有更多的问题, 就是对于1,2,2,2,3这个例子, 得到的结果直接就是错的; 我自己改写的java算法也是类似的, 根本就不对;
这个人后来自己给的解释:
@TonyLic said in A simple C++ solution in only 20 lines:
I figured out why. This method is based on that array is sorted. If using reference, swapping twice cannot maintain array sorted [pos ... n - 1] because nums[i] >= nums[pos]. However, using value and swapping once can keep array [pos...n - 1] sorted all the time.
@TonyLic said in A simple C++ solution in only 20 lines:
Making it sorted can only place equal numbers together, so you can skip dup by if(i != pos && nums[i] == nums[pos]) continue;
However, if you use swap twice and passing by reference, the array will not be sorted at some point, for example, 1,2,3,3 when pos = 0 and i = 2, you swap 1 and 3, which means now you have to get permutation of [2,1,3], it's not sorted.
那这个算法就大概看看了, 我不知道这种pass by value在c++里面有没有overhead, 反正java里面是完全没有办法这么做的, 每一个recursion iteration都单独来一个array copy, 复杂度直接炸了;
下面一个大神说话了:
@ofLucas said in A simple C++ solution in only 20 lines:
Backtracking is a nightmare for this problem.
The solution of "backtracking" is not efficient in spece since its creating arrays memories for each depth of the recursion function. If you do not pass by value, the swap action will disturb the sorted sequence and you are going to meet repeating answers.
One way to do it is to take advantage of nextPermutaion, which is to find the next larger permutation. And loop the nextPermutation function to find the complete unique permutation sequences.
Another way to solve it is DFS. DFS does not swap the array elements and preserves the sorted property.
For example you have want to solve permuteUnique[3,2,0,3,1,0,1]
Sort it you get
permuteUnique[0,0,1,1,2,3,3] =
0, permuteUnique[0,1,1,2,3,3]
1, permuteUnique[0,0,1,2,3,3]
2, permuteUnique[0,0,1,1,3,3]
3, permuteUnique[0,0,1,1,2,3]
and then you solve the sub question.
Sidenote: make sure in the current-depth DFS you don’t pick multiple duplicate and dig into sub-question.
public class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> ans = new ArrayList<List<Integer>>();
List<Integer> cur = new ArrayList<Integer>();
boolean[] used = new boolean[nums.length];
solve(0, nums, ans, cur, used);
return ans;
}
private void solve(int depth, int[] nums, List<List<Integer>> ans, List<Integer> cur, boolean[] used) {
if (depth == nums.length) {
ans.add(new ArrayList<Integer>(cur));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i] || (i > 0 && nums[i - 1] == nums[i] && !used[i - 1])) continue;
used[i] = true; cur.add(nums[i]);
solve(depth + 1, nums, ans, cur, used);
used[i] = false; cur.remove(cur.size() - 1);
}
}
}
说的可以说是非常到位了, 包括他的算法思路; 而且他对于backtracking和DFS的区分也是很清晰, 就类似我的mutating recursion vs. returned recursion的区别; 这题确实看到现在, 并没有一个纯正意义上的利用mutation的backtracking;
另外, 关于OP最开始的思路, 这里是一个小伙子不错的解释:
@BarneyZhao said in A simple C++ solution in only 20 lines:
Thanks for the explanation! I finally figured it out.
Yes, the reason of sorting is to skip duplicates. Take [1, 2, 2, 3] for example, when pos equals 0, we have below cases
(1,2,2,3) (pos = 0, i = 0)
(2,1,2,3) (pos = 0, i = 1)
(2,1,2,3) (pos = 0, i =2) skipped, since array[0]=array[2]; in other words, its subset (1,2,3) is the same as the second case (pos = 0, i=1)
(3,1,2,2) (pos = 0, i =3)
As we can see, the subset of the above four cases are still sorted. Amazing! Recursion continues.
On the other hand, if we use pass-by-reference, the set are ALWAYS sorted AFTER the extra swap, as below. The above amazing trick doesn’t work and duplicates won’t be avoided. So, the result of pass-by-reference algorithm is not correct.
(1,2,2,3) (pos = 0, i = 0)
(1,2,2,3) (pos = 0, i = 1)
(1,2,2,3) (pos = 0, i =2)
(1,2,2,3) (pos = 0, i =3)
讲的很到位了, 这里这个保证sorted的invariant, 是整个算法正确性的基础; 这个算法理解了之后, 真的是有点magic的感觉的;
另外, 注意他这里trace的是每一个iteration末尾的state;
这里才看出来为什么OP算法里面, 要让[i]和k比, 因为上一个被pick(到这个position)的element, 现在正在[i], 所以你循环到了[k]的时候, 应该跟[i]比, 假如有2,2这样的duplicate, 第一个2之后的所有的2都会被跳掉;
class Solution {
public List < List < Integer >> permuteUnique(int[] nums) {
List < List < Integer >> ans = new ArrayList < > ();
Arrays.sort(nums);
permutating(ans, nums, 0);
return ans;
}
private void permutating(List < List < Integer >> ans, int[] nums, int start) {
if (start == nums.length) {
List < Integer > li = new ArrayList < > ();
for (int n: nums) {
li.add(n);
}
ans.add(li);
return;
}
for (int i = start; i < nums.length; i++) {
if (i != start && nums[start] == nums[i]) {
continue;
}
swap(nums, start, i);
permutating(ans, Arrays.copyOf(nums, nums.length), start + 1);
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
java版本, 没啥好看的, 还是用的copy; 这个感觉就挺坑的;
@yetaila said in A simple C++ solution in only 20 lines:
First, note that any modification to the loop change the behavior of the loop. If you swap it back, the algorithm completely changes. It is not a straight forward algorithm. Try write down "12345" and simulate on paper to see how it changes. You will notice the difference between "swap them back" and "not swap them back".
That also answers why we cannot use reference(because we cannot swap everything back in each recursion level.)
另外, 如果真的一定要用指针:
@cfjmonkey said in A simple C++ solution in only 20 lines:
Nice code! I take quite a long time to understand this. In each loop, the num[i+1:] can keep its order as well. That's real interesting!
And a improvement to reduce the space complexity on the parameter num
class Solution {
public:
vector<vector<int> > resList;
vector<vector<int>> permute(vector<int>& nums) {
sort(nums.begin(), nums.end());
dfs(0, nums);
return resList;
}
void dfs(int i, vector<int>& nums){
if (i >= nums.size()){
resList.push_back(nums);
return;
}
int p;
for (p = i; p < nums.size(); p++){
if (p > i && nums[p] == nums[i]) continue;
swap(nums[i], nums[p]);
dfs(i + 1, nums);
}
int last = nums[i];
for (p = i + 1;p < nums.size(); p++)
nums[p - 1] = nums[p];
nums[p - 1] = last;
}
};
@SoumyaroopRoy said in A simple C++ solution in only 20 lines:
@cfjmonkey , that last for loop is just a left-rotate by 1 pos:
rotate(nums.begin() + i, nums.begin() + i + 1, nums.end());
这个算法大概思考一下, 是可以理解的; 比如你假设自己目前考虑的只有123(左边可能还有其他的, 但是我现在的i就是在这里[0]的位置); 那么你首先1保持, 然后123传下去, i等于1; 然后213传下去, i等于1, 注意, 然后这个DFS返回的时候, 我要用root level decision的思路来分析, 也就是我可以假设, 返回上来的时候, [1:]的sorted没有被破坏, 所以返回上来的还是213; 然后下一个iteration, 变成312, 然后i=1传下去, 返回上来还是312. 然后就关键了, 现在我自己i=0这个位置要开始返回了, 要返回给之前的结果, 这个时候你注意了, 你也要保证[i:]=[0:]是sorted! 然后你看这个小trace, 你就知道怎么做了;
严格来说, 如大家所说的, 这个算法真的是一点都不trivial, 从第一题的改变也不是那么轻松; 如果trace tree的分析技巧不娴熟, 很难正常时间内做完;
@WTIFS said in A simple C++ solution in only 20 lines:
Really takes me a lot of time to understand why not swapping back.
I'll give an example here.Take [1,2,
2] for example.step1: we get [1,2,
2].step2: [2,1,
2]. (swap 1 & 2)step3: [2,
2,1]. (swap2& 1)Back to step2: If we recover the numbers back to [1, 2,
2],
then in the nextforloop, we'll get [2, 2, 1], which is a duplicate. (swap2& 1)While if we do not recover the numbers, then the code
if (i != pos&& nums[i] == nums[pos])will prevent the swap of (2,2)
我不是一个人好吧, 妈的这个算法我也想了好久; 看起来这么这么简单, 背后真的是神机妙算;
@TransMatrix said in A non-recursive C++ implementation with O(1) space cost:
class Solution {
public:
vector<vector<int> > permuteUnique(vector<int> &S) {
// res.clear();
sort(S.begin(), S.end());
res.push_back(S);
int j;
int i = S.size()-1;
while (1){
for (i=S.size()-1; i>0; i--){
if (S[i-1]< S[i]){
break;
}
}
if(i == 0){
break;
}
for (j=S.size()-1; j>i-1; j--){
if (S[j]>S[i-1]){
break;
}
}
swap(S[i-1], S[j]);
reverse(S, i, S.size()-1);
res.push_back(S);
}
return res;
}
void reverse(vector<int> &S, int s, int e){
while (s<e){
swap(S[s++], S[e--]);
}
}
vector<vector<int> > res;
};
Basically, assume we have "1234", the idea is to increase the number in ascending order, so next is "1243", next is "1324", and so on.
这个也是之前其实见过的这题的另外一个思路, 用next permutation的思路来做; 因为NextPermutation这个算法本身是很成熟的, 所以直接用就可以了; 注意, 这个循环过程什么时候结束? 看他的循环里面的代码, i == 0的时候是唯一一个break while循环的点;
虽然我感觉这题用NextPermutation来做是有点剑走偏锋, 不过好歹也是一种方法; 而且是reduce到已经熟悉的问题, 不算过分;
另一种实现:
@weiwei2 said in A non-recursive C++ implementation with O(1) space cost:
yes,you are right.Actually,it is a problem similar to "Next Permutation", which rearranges numbers into the lexicographically next greater permutation of numbers. the difference between these two problems lies in how permutations we are required to generate.sorry,my English level is limited,hope this might help.
bool nextPermutation(vector<int> &num) {
int len=num.size()-1;
for(int pos=len-1;pos>=0;--pos){
if(num[pos]<num[pos+1]){
int smallNum=num[pos];
int lastPosBiggerThanSmallNum=
len-(find_if(num.rbegin(),
num.rend(),(bind2nd(greater<int>(),smallNum)))-
num.rbegin());
swap(num[pos],num[lastPosBiggerThanSmallNum]);
sort(num.begin()+pos+1,num.end());
return true;
}
}
return false;
}
vector<vector<int> > permuteUnique(vector<int> &num){
vector<vector<int> > res;
if(num.empty())
return res;
sort(num.begin(),num.end());
res.push_back(num);
while(nextPermutation(num)){
res.push_back(num);
}
return res;
}
这个方法的另外一个优势就是空间占用是O(1), 因为没有recursion Stack的要求;
@cbmbbz said in 9-line python solution with 1 line to handle duplication, beat 99% of others :-):
Very similar to Permutation I, see explanations in https://leetcode.com/discuss/19510/my-ac-simple-iterative-java-python-solution. To handle duplication, just avoid inserting a number before any of its duplicates.
def permuteUnique(self, nums):
ans = [object Object]
for n in nums:
new_ans = []
for l in ans:
for i in xrange(len(l)+1):
new_ans.append(l[:i]+[n]+l[i:])
if i<len(l) and l[i]==n: break #handles duplication
ans = new_ans
return ans
这个人之前第一题的做法其实我是看过的, 是一个更加纯粹的returned recursion, 虽然实际上不是用recursion来写的; 到了这题, 就看出来他的思路的优越性了, enforce order显得非常的直接, 逻辑也很清晰; 不过我感觉他代码的实际的逻辑好像跟他自己解说的有点不符合, 他这个好像是避免在之前已经插入的duplicate的后面重新插入;
@StefanPochmann said in 9-line python solution with 1 line to handle duplication, beat 99% of others :-):
Nice one! Here's an even shorter and I think faster implementation, though. Got it accepted in 100 ms, achieving the coveted "Your runtime beats 100.00% of python submissions." (Well, I tried five times, they were 112, 104, 100, 104 and 116 ms).
def permuteUnique(self, nums):
ans = [object Object]
for n in nums:
ans = [l[:i]+[n]+l[i:]
for l in ans
for i in xrange((l+[n]).index(n)+1)]
return ans
And for fun, a one-liner version:
def permuteUnique(self, nums):
return reduce(lambda a,n:[l[:i]+[n]+l[i:]for l in a for i in xrange((l+[n]).index(n)+1)],nums,[object Object])
不太清楚这里的Python语法, 不过这个index函数估计是获得rightmost index的意思? 反正大概意思还是按照原来OP的写法来理解;
@zjufisher said in 9-line python solution with 1 line to handle duplication, beat 99% of others :-):
Very smart way to eliminate the duplicate.
Here is my understanding about the eliminate process.After several times of append and other operations,
here I just pay attention to one element, 2's position in the inner list
We get the current list like below:
- [2,x,x,x]
- [x,2,x,x]
- [x,x,2,x]
- [x,x,x,2]
Of course if we replace the "x" with other elements, there should be several other lists in each row,but the position of "2" should just be same,[0],[1],[2],[3] for each row.
The approach will traverse each list and insert the new element.
If the new element is "2", the current "for loop" will break.
Therefor,after the two loops,the "2" 's position in the list should be:
[0,1]
[0,2],[1,2]
[0,3],[1,3],[2,3]
[0,4],[1,4],[2,4],[3,4]
It will actually cover all the situation of the two 2's distribution.
这个解释的还可以, 不过这个OP的算法的最大的有点, 我认为还是其实可以相对比较declarative的理解; 所以这样特别imperative的去想, 并不是十分的必要;
@chenweisomebody said in 9-line python solution with 1 line to handle duplication, beat 99% of others :-):
It is easy to come up with we should skip the same number we meet. But that only covers intra-perm, like from “2,1” to “2,2,1” and “2,2,1”, how about the inter-perm duplicate, like from “2,1” to “2,1,2” and from “1,2” to “2,1,2”.
When we first encounter the situation from “2,1” to “2,2,1” and “2,2,1”, if we choose to “continue” and we will insert new “2” into rightmost position to get “2,1,2” which duplicates “2,1,2” later from “1,2”.
Why? First we start from permutation “---orig_num---” and insert new number from left to right. Once the new number is inserted right of its duplicate number, it looks like “---orig_num---insert_num---”, which can be observed as “---new_num---orig_num---” extended from another permutation “---orig_num---” by inserting insert_num at left position. Because we operate on all permutations generated from previous loop, we can always find a previous permutation to cause inter-permation duplicate.
Therefore, we should “break”, other than “continue”, after we encounter the first same number.
这个理解虽然也是有点太imperative, 不过讲的还是很对的;
submission最优解:6(98):
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> ret = new ArrayList<>();
helper(nums, ret, 0);
return ret;
}
private void helper(int[] nums, List<List<Integer>> ret, int index) {
int len = nums.length;
if (index == len - 1) {
List<Integer> list = new ArrayList<>();
for (int num : nums) list.add(num);
ret.add(list);
return;
}
for (int i = index; i < len; i++) {
boolean flag = false;
for (int j = index; j < i; j++) {
if (nums[j] == nums[i]) {
flag = true;
break;
}
}
if (flag) continue;
int tmp = nums[index];
nums[index] = nums[i];
nums[i] = tmp;
helper(nums, ret, index + 1);
tmp = nums[index];
nums[index] = nums[i];
nums[i] = tmp;
}
}
}//improved
不是很看得懂, 画了两个trace:
这个题目学的一个重要的技能点就是recursion trace的熟练度; 这里这两种画法, 都是告诉你熟悉一下; 其实实际上第二种画起来更简单, 更直观一些; 注意我的蓝色小箭头代表的是iteration内部i的循环位置;
注意, 他这个代码跟之前看过的一个判断i > index && nums[i] == nums[index]然后skip的写法非常的类似, 但是那个写法我们已经证明过是错的了; 而这里这个写法, 即使是不sort, 也是对的; 而那个写法还依赖sort;
这里这个写法, 判断的是[i]跟[index:i]之间的所有的不重复, 而不是[i]跟[index]之间的不重复; 看看上面的trace, 好像也不是很难理解; 首先, j = index的时候是不判断的, 也就是i = index的时候, 是不判断的; 然后后面的, 我们准备把[i]放到[index]的位置, 然后下面就在[index + 1:]上面recurse了, [index]的位置就定死了要放[i], 那么我们只要保证[i]没有在[index:i], 也就是当前的[i]之前被用过就行了;
看起来很直接, 不知道是不是漏掉了什么东西; 另外, 他这个写法感觉可以pre compute一个表格来加速运算;
试了一下, 发现实际上是不能的, 写的是这个算法:
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> res_lss = new ArrayList<> ();
boolean[][] contains = new boolean[nums.length][nums.length];
for (int i = nums.length - 1; i >= 0; i--) {
boolean success = false;
for (int j = i - 1; j >= 0; j--) {
if (!success && nums[j] == nums[i])
success = true;
contains[j][i] = success;
}
}
dfs (nums, 0, res_lss, contains);
return res_lss;
}
void dfs (int[] nums, int start, List<List<Integer>> lss, boolean[][] contains) {
if (start == nums.length - 1) {
List<Integer> ls = new ArrayList<> ();
for (int num : nums)
ls.add (num);
lss.add (ls);
return;
}
for (int i = start; i < nums.length; i++) {
if (contains[start][i])
continue;
swap (nums, start, i);
dfs (nums, start + 1, lss, contains);
swap (nums, start, i);
}
}
void swap (int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
String array (int[] nums) {
return Arrays.deepToString (new int[][] {nums});
}
String wrap (String s, int code) {
return (char) 27 + "[" + code + "m" + s + (char) 27 + "[0m";
}
}
但是有一个事情你忘记了, 你这个contains判断的始终是一开始的nums的情况; 在往下走的level里面, 这个nums是已经被permute过了的;
总体来说, 我认为这个算法可以说是这个题目的最佳算法了, 因为相对于第一题的算法, 改动最小; 只要加一个直观上的去重处理就能完美处理第二题: 而且因为是有undo的backtracking, 所以理解起来也比较简单; 其他方法全都是依赖sort之后通过order之类的信息来去重;
Problem Description
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,
[1,1,2] have the following unique permutations:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
Difficulty:Medium
Total Accepted:151.4K
Total Submissions:438.7K
Contributor:LeetCode
Companies
microsoftlinkedin
Related Topics
backtracking
Similar Questions
Next PermutationPermutationsPalindrome Permutation II