Java Solution without sort


  • 0
    N

    The idea is to "number" the values in arrays, so that the second "1" must shows after the first "1".
    That's why I reversely iterating the list, so that we could break upon meeting an existing element.

        public List<List<Integer>> permuteUnique(int[] nums) {
            return permute(nums,0);
        }
        
        private List<List<Integer>> permute(int[] nums, int start) {
            List<List<Integer>> res = new ArrayList<List<Integer>>();
            // if last element
            if (start == nums.length-1) {
                List<Integer> one = new ArrayList<Integer>();
                one.add(nums[start]);
                res.add(one);
                return res;
            }
            
            // for all permutation, try add current nums[start]
            Iterator<List<Integer>> it = permute(nums, start+1).iterator();
            while(it.hasNext()) {
                List<Integer> cur = it.next();
                for(int i = cur.size(); i >=0; i--) {
                    List<Integer> tmp = new ArrayList<Integer>(cur);
                    tmp.add(i, nums[start]);
                    res.add(tmp);
                    // stop when find the same element
                    if (i > 0 && nums[start] == cur.get(i-1)) break;
                }
            }
            return res;
        }

  • 0
    Q

    Good idea, it is noted that your method will use very large space, easy to cause MLE.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.