Permutations in Array

Summary

Given an array of integers, generate all possible permutations of the given array. The goal is to create a program that can produce all unique arrangements of the elements in the array.

Detailed Explanation

To solve this problem, we will use recursion to generate all possible permutations. We start by fixing one element at a time and generating all permutations of the remaining elements. This process continues until we have exhausted all possible combinations.

Here's the step-by-step approach:

1. Fix an element from the array.
2. Recursively generate all permutations of the remaining elements.
3. Add the fixed element to each permutation generated in step 2.
4. Continue this process for all elements in the array.
5. Return the list of all permutations.

The time complexity of this approach is O(n!), where n is the number of elements in the array, because we are generating all possible permutations. The space complexity is also O(n!), as we need to store all the permutations.

Optimized Solutions

Java

java
import java.util.*;

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

    private static void backtrack(List<List<Integer>> result, List<Integer> tempList, int[] nums) {
        if (tempList.size() == nums.length) {
            result.add(new ArrayList<>(tempList));
        } else {
            for (int i = 0; i < nums.length; i++) {
                if (tempList.contains(nums[i])) {
                    continue;
                }
                tempList.add(nums[i]);
                backtrack(result, tempList, nums);
                tempList.remove(tempList.size() - 1);
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        List<List<Integer>> result = permute(nums);
        for (List<Integer> permutation : result) {
            System.out.println(permutation);
        }
    }
}

Python

python
def permute(nums):
    def backtrack(result, tempList, nums):
        if len(tempList) == len(nums):
            result.append(list(tempList))
        else:
            for i in range(len(nums)):
                if nums[i] not in tempList:
                    tempList.append(nums[i])
                    backtrack(result, tempList, nums)
                    tempList.remove(tempList[-1])
    result = []
    backtrack(result, [], nums)
    return result

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

C++

cpp
#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> result;
    backtrack(result, {}, nums);
    return result;
}

void backtrack(vector<vector<int>>& result, vector<int> tempList, vector<int>& nums) {
    if (tempList.size() == nums.size()) {
        result.push_back(tempList);
    } else {
        for (int i = 0; i < nums.size(); i++) {
            if (find(tempList.begin(), tempList.end(), nums[i]) != tempList.end()) {
                continue;
            }
            tempList.push_back(nums[i]);
            backtrack(result, tempList, nums);
            tempList.pop_back();
        }
    }
}

int main() {
    vector<int> nums = {1, 2, 3};
    vector<vector<int>> result = permute(nums);
    for (const auto& permutation : result) {
        cout << permutation << endl;
    }
    return 0;
}

JavaScript

javascript
function permute(nums) {
    function backtrack(result, tempList, nums) {
        if (tempList.length === nums.length) {
            result.push([...tempList]);
        } else {
            for (let i = 0; i < nums.length; i++) {
                if (!tempList.includes(nums[i])) {
                    tempList.push(nums[i]);
                    backtrack(result, tempList, nums);
                    tempList.pop();
                }
            }
        }
    }
    let result = [];
    backtrack(result, [], nums);
    return result;
}

let nums = [1, 2, 3];
console.log(permute(nums));

Note: The code for all languages generates the permutations and prints them to the console.