permutationII疑问

1. public class Solution {
   
2.     public List<List<Integer>> permuteUnique(int[] nums) {
   
3.         List<List<Integer>> res = new ArrayList<List<Integer>>();
   
4.         List<Integer> rows = new ArrayList<Integer>();
   
5.         if(nums == null || nums.length == 0)
   
6.             return res;
   
7.         Arrays.sort(nums);
   
8.         boolean[] record = new boolean[nums.length];
   
9.         dfs(nums, record, res, rows);
   
10.         return res;
    
11.     }
    
12.     public void dfs(int[] nums, boolean[] record, List<List<Integer>> res, List<Integer> rows) {
    
13.         if(nums.length == rows.size()) {
    
14.             if(!res.contains(rows))
    
15.             res.add(new ArrayList<Integer>(rows));
    
16.             return ;
    
17.         }
    
18.         for(int i = 0; i < nums.length; i++) {
    
19.             //if(i > 0 && nums[i]==nums[i-1] && record[i - 1] == false)
    
20.               //  continue;            
    
21.             if(record[i] == false) {
    
22.                 rows.add(nums[i]);
    
23.                 record[i] = true;
    
24.                 dfs(nums, record, res, rows);
    
25.                 record[i] = false;
    
26.                 rows.remove(rows.size() - 1);
    
27.                 //while(i < nums.length - 1 && nums[i] == nums[i+1])
    
28.                   //  i++;
    
29.             }
    
30.             
    
31.         }
    
32.         return ;
    
33.     }
    
34. }

复制代码

各路大神，我想问下这道题这样写为什么会超时。。。写subsetII时用contains明明是可以通过的，这里为什么不行了。。。谢谢了！

zh355245849 发表于 2015-7-4 18:01
哦，也就是说用            if(!res.contains(rows))  来检查比下面的查重废很多时间是吗，因为把所有的 ...

可以这样理解。Backtracking中很重要的一步就是剪枝（pruning），也就是当发现当前这条路没有前途时，应该立刻放弃掉。而如果像原来的代码中那样，等于是放弃了剪枝。那么很多本来在看到第一个数字就能否决的伪solution，现在要将其的全部数字都处理一遍才能否决。如果数组中重复字符非常多，伪solution的个数可能会远超过真solution的个数。所以程序的实际运行时间将非常有可能达到该算法的时间复杂度的上限O(N!)。

为什么把重复性检查的代码注释掉了？这题如果不检查重复性的话，如果遇到很长的重复字串，比如aaaaaaaaaaaaa.....b这样的测试用例时非常容易超时。至于为何Subset不会超时，这也不难理解。Subset的复杂度是O(N*2^N)，Permutation的复杂度则是O(N*N!)。后者比前者要大的多。如果两题的测试用例长度差不多，那么完全有可能出现前者AC，后者TLE的情况。

stellari 发表于 2015-7-4 17:57
为什么把重复性检查的代码注释掉了？这题如果不检查重复性的话，如果遇到很长的重复字串，比如aaaaaaaaaaaa ...

哦，也就是说用            if(!res.contains(rows))  来检查比下面的查重废很多时间是吗，因为把所有的都执行了一遍？。。不知道我理解的对不对。。。

zh355245849 发表于 2015-7-4 18:01
哦，也就是说用            if(!res.contains(rows))  来检查比下面的查重废很多时间是吗，因为把所有的 ...

你把解空间树的结构画出来你就知道了。如果你用hash去重，你实际上还是要去走一些重复的path后直到排列的数字个数到位时再去hash判断。而我们说剪枝是你在探索某个child nodes时发现，如果从这个child node探索下去和之前的child node探索下去的结果重复的，那么立马剪枝掉。相当于后者避免了那些重复的运算和探索过程，而前者还是要去探索直到递归终止时才判断是否重复，那么这之间消耗的时间对于一些比较特殊的test case的时候就容易TLE

我认为这题的testcase或者benchmark后来有修改 我早先也是Backtrack做是可以AC的，前两天做就不行了，包括之前可以AC的都不行了,后来优化了半天怎么都不行。后来看了看discuss, 现在比较好的方法是用next permutation那题的算法。先从升序排列开始，然后不断产生以下一个更大的Permutation直到倒序排列 这样可以用iterative的方法不重复的生成每一个permutation

glaciersilent 发表于 2015-7-5 05:26
我认为这题的testcase或者benchmark后来有修改 我早先也是Backtrack做是可以AC的，前两天做就不行了，包括 ...

请问你用的什么语言？LC近来确实有不少改动，不过我刚刚用C++和Java测试了一下，分别是32ms和388ms（用的都是Backtracking），这离后台设定的TLE阈值还有距离。AC应该是不成问题的。

能否让我看看你的TLE代码？

glaciersilent 发表于 2015-7-5 05:26
我认为这题的testcase或者benchmark后来有修改 我早先也是Backtrack做是可以AC的，前两天做就不行了，包括 ...

同意，感觉用next permutation既容易写，也符合直观思维。有些情形下递归反倒没有循环好写。

stellari 发表于 2015-7-5 10:56
请问你用的什么语言？LC近来确实有不少改动，不过我刚刚用C++和Java测试了一下，分别是32ms和388ms（用的 ...

用的java语言。。我贴的这个就是TLE的。。。

zh355245849 发表于 2015-7-5 13:15
用的java语言。。我贴的这个就是TLE的。。。

噢，不好意思，我是说想看看@glaciersilent 的代码。楼主的代码没有剪枝，TLE并非意料之外。