DEV Community

Prashant Mishra
Prashant Mishra

Posted on

Pattern: Permutations

#dsa #leetcode #permutations

A Permutations is rearrangement of all the elements of the array.
Example:
Permutations

class Solution {
    List<List<Integer>> list = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        int taken[] = new int[nums.length];
        permute(nums, taken, new ArrayList<>());
        return list;
    }
    public void permute(int nums[], int [] taken, List<Integer> l){
        if(l.size()== nums.length){
            list.add(new ArrayList<>(l));
            return;
        }
        for(int i = 0;i< nums.length;i++){
            if(i>0 && nums[i]==nums[i-1] && taken[i-1]==1) continue;
            if(taken[i]==0){
                taken[i] = 1;
                l.add(nums[i]);
                permute(nums,taken,l);
                l.remove(l.size()-1);
                taken[i]=0;
            }
        }
    }
}
Enter fullscreen mode Exit fullscreen mode

Example 2: Permutation II - get unique permutations

class Solution {
    List<List<Integer>> list = new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        int taken[] = new int[nums.length];
        permute(nums, taken, new ArrayList<>());
        return list;  
    }
    public void permute(int nums[], int [] taken, List<Integer> l){
        if(l.size()== nums.length){
            list.add(new ArrayList<>(l));
            return;
        }
        for(int i = 0;i< nums.length;i++){
            //If previous duplicate is NOT used → skip current
            if(i>0 && nums[i]==nums[i-1] && taken[i-1]==0) continue;
            if(taken[i]==0){
                taken[i] = 1;
                l.add(nums[i]);
                permute(nums,taken,l);
                l.remove(l.size()-1);
                taken[i]=0;
            }
        }
    }
}
Enter fullscreen mode Exit fullscreen mode

Top comments (1)

Collapse
 
xiaoming_nian_94953c8c9b8 profile image
Andy Nian •

Sorting the array to deal with duplicates before generating permutations is a smart move. It helps the algorithm skip duplicates efficiently. I'm wondering about the performance impact when the array has lots of duplicates—does the sorting really make it worth it? I've been using prachub.com for coding interview prep, and their permutation problems cover follow-up questions I encountered in interviews. They have company-tagged coding banks that are more relevant than just browsing random threads on StackOverflow.