Generate Permutations of an array

JavaView on GFG

Problem Overview

Generate all permutations of an array.

See our study guide for structured GFG and LeetCode practice.

Intuition

Generate all permutations of an array. Backtracking with swap-at-current-position.

Algorithm

1Backtrack: swap arr[start] with arr[i] for i in start..n-1. Recurse with start+1. Swap back.

Common Pitfalls

• Same as LC 46. O(n! * n) total. For unique elements only. For duplicates: sort and skip duplicates.

Generate Permutations of an array.java

Java

// Approach: Backtracking with swap-in-place. Swap each element to current position and recurse.
// Time: O(n! * n) Space: O(n)
import java.util.*;

class Solution {
    public static ArrayList<ArrayList<Integer>> permuteDist(int[] arr) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        int n = arr.length;

        ArrayList<Boolean> freq = new ArrayList<>();
        for (int i = 0; i < n; i++)
            freq.add(false);

        solve(arr, res, new ArrayList<>(), freq);
        return res;
    }

    static void solve(int[] arr,
            ArrayList<ArrayList<Integer>> res,
            ArrayList<Integer> li,
            ArrayList<Boolean> freq) {

        if (li.size() == arr.length) {
            res.add(new ArrayList<>(li));
            return;
        }

        for (int i = 0; i < arr.length; i++) {
            if (!freq.get(i)) {
                freq.set(i, true);
                li.add(arr[i]);

                solve(arr, res, li, freq);

                // backtrack
                li.remove(li.size() - 1);
                freq.set(i, false);
            }
        }
    }
};

Was this solution helpful?