Yet another Java solution, using HashSet


  • 1
    J

    It's almost the same as the previous Permutations problem, the key is to identify how duplicates are generated. On each level of recursion, for every number that is swapped to the index , it creates a new branch of results. Thus if same digit get swapped to index for multiple times, duplicates are created. So to avoid duplicates, simply add a HashSet to filter out repeating digits.

    Time complexity O(N!)

    public class Solution {
        private void generate(int index, int[] nums, List<List<Integer>> res) {
            if (index == nums.length - 1) {
                List<Integer> list = new ArrayList<>(nums.length);
                for (int n: nums) list.add(n);
                res.add(list);
            } else {
                HashSet<Integer> chosen = new HashSet<>();
                for (int i = index; i < nums.length; i++) {
                    if (chosen.add(nums[i])) {
                        swap(nums, i, index);
                        generate(index + 1, nums, res);
                        swap(nums, i, index);
                    }
                }
            }
        }
        private void swap(int[] nums, int l, int r) {
            int t = nums[l];
            nums[l] = nums[r];
            nums[r] = t;
        }
        public List<List<Integer>> permuteUnique(int[] nums) {
            List<List<Integer>> res = new ArrayList<>();
            generate(0, nums, res);
            return res;
        }
    }
    

Log in to reply
 

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