Permutation based on swap, beat 98%


  • 0
    M
    public class Solution {
        public List<List<Integer>> permuteUnique(int[] nums) {
            Arrays.sort(nums);
            List<List<Integer>> res = new ArrayList<>();
            permute(nums, 0, res);
            return res;
        }
        
        private void permute(int[] nums, int pos, List<List<Integer>> res){
            if(pos>=nums.length){
                List<Integer> list = new ArrayList<>();
                for(int num : nums) {
                    list.add(num);
                }
                res.add(list);
                return;
            }
            for(int i=pos; i<nums.length; i++){
                if(i!=pos && (nums[i]==nums[i-1] || nums[pos]==nums[i])) continue;
                swap(nums, i, pos);
                permute(nums, pos+1, res);
            }
            for ( int i = pos; i+1 < nums.length; i++ ) {
                swap(nums, i, i+1);
            }
        }
        
        private void swap(int[] nums, int i, int j){
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }
    

    The swapped array will keep the sorted order by for swap loop.


Log in to reply
 

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