Simple Java Solution based on Permutation I


  • 0
    S
    public List<List<Integer>> permuteUnique(int[] nums) {
            List<List<Integer>> result = new LinkedList<List<Integer>>();
            List<Integer> list = new LinkedList<Integer>();
            HashSet<Integer> visit = new HashSet<Integer>(); // visit set prevents traversing elements that're already visited.
            permuteUnique(result, list, nums, visit);
            return result;
        }
        
        public void permuteUnique(List<List<Integer>> result, List<Integer> list, int[] nums, HashSet<Integer> visit) {
            if (list.size() >= nums.length) {
                result.add(new LinkedList<Integer>(list));
                return;
            }
            HashSet<Integer> duplicate = new HashSet<Integer>(); // duplicate set prevent traversing same element e.g. [1, 1, 2] the second 1 will be skipped.
            for (int i = 0; i < nums.length; i++) {
                if (visit.contains(i) || duplicate.contains(nums[i])) continue;
                list.add(nums[i]);
                duplicate.add(nums[i]);
                visit.add(i);
                permuteUnique(result, list, nums, visit);
                list.remove(list.size() - 1);
                visit.remove(i);
            }
        }
    

Log in to reply
 

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