Simple 4ms Java code using HashSet and Swap with in-line comments


  • 0
    H
    public class Solution {
        public List<List<Integer>> permuteUnique(int[] nums) {
            List<List<Integer>> result = new ArrayList();
            perm(result, nums, 0);
            return result;
        }
        // Perm - Fix all previous nums, and permute the nums in {nums[start], ..., nums[n-1]} 
        private static void perm(List<List<Integer>> result, int[] nums, int start) {
            if (start == nums.length-1) {
                List<Integer> numList = new ArrayList(nums.length);
                for (int i = 0; i < nums.length; i++) {
                    numList.add(nums[i]);
                }
                result.add(numList);
                return;
            }
            // The basic idea is to fix the prev nums and permute the last two.
            // Then permute the last three, then last four and so forth.
            // To avoid duplication, we only swap with those nums which haven't
            // been swapped with.
            Set<Integer> swapped = new HashSet();
            for (int i = start; i < nums.length; i++) {
                if (swapped.contains(nums[i])) continue;
                int temp = nums[start];
                nums[start] = nums[i];
                nums[i] = temp;
                
                perm(result, nums, start+1);
                
                temp = nums[start];
                nums[start] = nums[i];
                nums[i] = temp;
                swapped.add(nums[i]);
            }
        }
    }
    

Log in to reply
 

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