All Unique Permutations of an array

JavaView on GFG

Intuition

Generate all unique permutations of array with duplicates. Sort + backtrack with skip-duplicates logic.

Algorithm

1Sort array. Backtrack: for each position, skip if arr[i]==arr[i-1] and i-1 not used. Swap and recurse.

Common Pitfalls

•Same as LC 47. Must sort first. Skip duplicate choices at same recursion level to avoid repeat permutations.

All Unique Permutations of an array.java

Java

// Approach: Sort array, then backtrack with a 'used' boolean array.
// Skip duplicate elements at the same recursion depth to avoid duplicate permutations.
// Time: O(n! * n) Space: O(n)
import java.util.*;

class Solution {
    public static ArrayList<ArrayList<Integer>> uniquePerms(int[] arr) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        Arrays.sort(arr);
        do {
            ArrayList<Integer> perm = new ArrayList<>(arr.length);
            
            for (int x : arr)
                perm.add(x);
            res.add(perm);

        } while (nextPermutation(arr));

        return res;
    }

    private static boolean nextPermutation(int[] a) {
        int n = a.length;
        int i = n - 2;
        while (i >= 0 && a[i] >= a[i + 1])
            i--;

        if (i < 0)
            return false;

        int j = n - 1;
        while (a[j] <= a[i])
            j--;

        swap(a, i, j);
        reverse(a, i + 1, n - 1);

        return true;
    }

    private static void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    private static void reverse(int[] a, int l, int r) {
        while (l < r)
            swap(a, l++, r--);
    }
};

Was this solution helpful?