Question 32 : Permutations of array in java.

 Given array of distinct integers, print all permutations of the array.

For example :

array : [10, 20, 30]
 
Permuations are :
 
[10, 20, 30]
[10, 30, 20]
[20, 10, 30]
[20, 30, 10]
[30, 10, 20]
[30, 20, 10]

We can solve the problem with the help of recursion. It is quite hard to explain recursion, so I have created a recursion tree to demonstrate it.

Here is the code for the same.

import java.util.ArrayList;
import java.util.List;
 
public class PermutateArray {
 
    public static void main(String[] args) {
        PermutateArray pa=new PermutateArray();
 
        int[] arr= {10, 20, 30};
 
        List<List<Integer>> permute = pa.permute(arr);
 
        System.out.println("Permuations of array : [10, 20, 30] are:");
        System.out.println("=========================================");
        for(List<Integer> perm:permute)
        {
            System.out.println(perm);
        }
 
    }
    public List<List<Integer>> permute(int[] arr) {
        List<List<Integer>> list = new ArrayList<>();
        permuteHelper(list, new ArrayList<>(), arr);
        return list;
    }
 
    private void permuteHelper(List<List<Integer>> list, List<Integer> resultList, int [] arr){
 
        // Base case
        if(resultList.size() == arr.length){
            list.add(new ArrayList<>(resultList));
        } 
        else{
            for(int i = 0; i < arr.length; i++){ 
 
                if(resultList.contains(arr[i])) 
                {
                    // If element already exists in the list then skip
                    continue; 
                }
                // Choose element
                resultList.add(arr[i]);
                // Explore
                permuteHelper(list, resultList, arr);
                // Unchoose element
                resultList.remove(resultList.size() - 1);
            }
        }
    } 

When you run above program, you will get below output:

Permuations of array : [10, 20, 30] are:
=========================================
[10, 20, 30] [10, 30, 20] [20, 10, 30] [20, 30, 10] [30, 10, 20] [30, 20, 10]

have illustrated how recursion is working here with below diagram.

Problem 2

Given array of integers(can contain duplicates), print all permutations of the array.

---

Solution

We can solve this using recursion as well but need to take care of duplicates.We will sort the array, so all duplicates will be conitguous.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
 
public class PermuteArrayWithDuplicates {
 
    public static void main(String[] args) {
        PermuteArrayWithDuplicates pa=new PermuteArrayWithDuplicates();
 
        int[] arr= {10, 20, 10};
 
        List<List<Integer>> permute = pa.permute(arr);
 
        System.out.println("Permuations of array : [10, 20, 10] are:");
        System.out.println("=========================================");
        for(List<Integer> perm:permute)
        {
            System.out.println(perm);
        }
 
    }
    public List<List<Integer>> permute(int[] arr) {
        List<List<Integer>> list = new ArrayList<>();
        Arrays.sort(arr);
        permuteHelper(list, new ArrayList<>(), arr,new boolean[arr.length]);
        return list;
    }
 
    private void permuteHelper(List<List<Integer>> list, List<Integer> resultList, int [] arr, boolean [] used){
 
        // Base case
        if(resultList.size() == arr.length){
            list.add(new ArrayList<>(resultList));
        } else{
            for(int i = 0; i < arr.length; i++){
                if(used[i] || i > 0 && arr[i] == arr[i-1] && !used[i - 1]) 
                {   
                        // If element is already used
                        continue;
                }
                // choose element
                used[i] = true; 
                resultList.add(arr[i]);
 
                // Explore
                permuteHelper(list, resultList, arr, used);
 
                // Unchoose element
                used[i] = false; 
                resultList.remove(resultList.size() - 1);
            }
        }
    }
 
}

Permuations of array : [10, 20, 10] are:
=========================================
[10, 10, 20] [10, 20, 10] [20, 10, 10]

Recursive Backtracking (Standard Approach)
This is the most common and efficient way to generate permutations.
🟦 Java
import java.util.*;

public class ArrayPermutations {

    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> results = new ArrayList<>();
        backtrack(nums, 0, results);
        return results;
    }

    private static void backtrack(int[] nums, int index, List<List<Integer>> results) {
        if (index == nums.length) {
            List<Integer> permutation = new ArrayList<>();
            for (int num : nums) {
                permutation.add(num);
            }
            results.add(permutation);
            return;
        }

        for (int i = index; i < nums.length; i++) {
            swap(nums, index, i);
            backtrack(nums, index + 1, results);
            swap(nums, index, i); // backtrack
        }
    }

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

🐍 Python
def permute(nums):
    results = []
    
    def backtrack(start):
        if start == len(nums):
            results.append(nums.copy())
            return
        for i in range(start, len(nums)):
            nums[start], nums[i] = nums[i], nums[start]
            backtrack(start + 1)
            nums[start], nums[i] = nums[i], nums[start]  # backtrack

    backtrack(0)
    return results

print(permute([1,2,3]))


🟡 2️⃣ Using Heap’s Algorithm (Efficient Swap-Based)
Heap’s algorithm systematically generates each permutation by swapping. 
🟦 Java
import java.util.*;

public class HeapPermutations {

    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> results = new ArrayList<>();
        generate(nums.length, nums, results);
        return results;
    }

    private static void generate(int k, int[] nums, List<List<Integer>> results) {
        if (k == 1) {
            List<Integer> permutation = new ArrayList<>();
            for (int n : nums) {
                permutation.add(n);
            }
            results.add(permutation);
        } else {
            generate(k - 1, nums, results);
            for (int i = 0; i < k - 1; i++) {
                if (k % 2 == 0) {
                    swap(nums, i, k - 1);
                } else {
                    swap(nums, 0, k - 1);
                }
                generate(k - 1, nums, results);
            }
        }
    }

    private static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}

🐍 Python
def heap_permute(nums):
    results = []

    def generate(k, arr):
        if k == 1:
            results.append(arr.copy())
        else:
            generate(k - 1, arr)
            for i in range(k - 1):
                if k % 2 == 0:
                    arr[i], arr[k - 1] = arr[k - 1], arr[i]
                else:
                    arr[0], arr[k - 1] = arr[k - 1], arr[0]
                generate(k - 1, arr)

    generate(len(nums), nums)
    return results


  
    
    
    
    
  

  

    

Approach
    
Time Complexity
    
Space Complexity
    
Best Use
  

  

    

      Recursive Backtracking
    
    

      O(n × n!)
    
    

      O(n!)
    
    

      ⭐ Simple & standard
    
  

  

    

      Heap’s Algorithm
    
    

      O(n × n!)
    
    

      O(n!)
    
    

      ✔ Minimizes swap operations