Simple solution Java O(N) space without hashmap with sorting


  • 0
    I
    public class Solution {
        public List<List<Integer>> permuteUnique(int[] nums) {
            List<List<Integer>> res = new ArrayList<List<Integer>>();
            Integer[] cand = new Integer[nums.length];
            
            Arrays.sort(nums);
            permute(res, cand, nums, 0, 0);
            
            return res;
        }
        
        private void permute(List<List<Integer>> res, Integer[] cand, int[] nums, int pos, int from) {
            if(pos == cand.length) {
                res.add(new ArrayList<Integer>(Arrays.asList(cand)));
                return;
            }
            
            for(int i = from; i < nums.length; i++) {
                if(cand[i] == null) {
                    boolean skipper = pos + 1 < nums.length && nums[pos + 1] == nums[pos];
                    cand[i] = nums[pos];
                    permute(res, cand, nums, pos + 1, skipper ? i + 1 : 0);
                    cand[i] = null;
                }
            }
            
        }
    }
    

Log in to reply
 

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