📚 Permutations Pattern – Java Cheat Sheet

📌 What Is It?

The Permutations Pattern is used to generate all possible arrangements of a given set of elements. This pattern is commonly used in problems involving permutations, arrangements, and ordering.

🧱 Pattern Templates

1️⃣ Recursive Backtracking Approach

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        generatePermutations(nums, new boolean[nums.length], new ArrayList<>(), result);
        return result;
    }

    private void generatePermutations(int[] nums, boolean[] used, List<Integer> current, List<List<Integer>> result) {
        if (current.size() == nums.length) {
            result.add(new ArrayList<>(current));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            used[i] = true;
            current.add(nums[i]);
            generatePermutations(nums, used, current, result);
            current.remove(current.size() - 1); // Backtrack
            used[i] = false;
        }
    }
}

2️⃣ Iterative Approach (Heap's Algorithm)

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> numsList = new ArrayList<>();
        for (int num : nums) numsList.add(num);
        generatePermutations(numsList, nums.length, result);
        return result;
    }

    private void generatePermutations(List<Integer> nums, int n, List<List<Integer>> result) {
        if (n == 1) {
            result.add(new ArrayList<>(nums));
            return;
        }

        for (int i = 0; i < n; i++) {
            generatePermutations(nums, n - 1, result);
            if (n % 2 == 0) {
                Collections.swap(nums, i, n - 1);
            } else {
                Collections.swap(nums, 0, n - 1);
            }
        }
    }
}

3️⃣ Using Next Permutation

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums); // Start with the smallest permutation
        do {
            List<Integer> current = new ArrayList<>();
            for (int num : nums) current.add(num);
            result.add(current);
        } while (nextPermutation(nums));
        return result;
    }

    private boolean nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) i--;
        if (i < 0) return false;

        int j = nums.length - 1;
        while (nums[j] <= nums[i]) j--;
        swap(nums, i, j);

        reverse(nums, i + 1, nums.length - 1);
        return true;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            swap(nums, start++, end--);
        }
    }
}

📊 Time Complexity

Recursive Backtracking: O(N!), where N is the size of the input array.
Heap's Algorithm: O(N!), as it generates all permutations.
Next Permutation: O(N! * N), as it generates all permutations and sorts them.

✅ Use Cases

Generating all permutations of a set
Finding arrangements or orderings
Solving problems involving permutations

📘 Common LeetCode Problems

46. Permutations [Medium] Backtracking
47. Permutations II [Medium] Backtracking

🧪 Example: Permutations

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Explanation:
- The permutations of [1,2,3] are generated using backtracking, Heap's algorithm, or next permutation.

💡 Pro Tips

Use backtracking for flexibility and simplicity.
Heap's algorithm is efficient for generating permutations iteratively.
Next permutation is useful when permutations need to be generated in lexicographical order.
Edge cases: empty input, single-element input.