Permutations

Problem Statement

The task requires generating all possible permutations of a given array of distinct integers, nums. A permutation of an array is a rearrangement of its elements. You are to return the permutations in any order. Each integer in the array is unique and can range from -10 to 10.

Examples

Example 1

Input:

nums = [1,2,3]

Output:

[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2

Input:

nums = [0,1]

Output:

[[0,1],[1,0]]

Example 3

Input:

nums = [1]

Output:

[[1]]

Constraints

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• All the integers of nums are unique.

Approach and Intuition

Understanding Permutations

Permutations involve arranging elements of a set in all possible orders. For an array nums of length n, there are n! (factorial of n) permutations. The factorial function usually grows very quickly, which informs our constraints on the maximum array length.

Example Analysis

1. Example 1:

   • Input: nums = [1,2,3]
   • Output: All permutations of [1,2,3].
   • As nums has 3 elements, there should be 3! = 6 permutations. These include arrangements such as [1,2,3], where we start with 1 and permute 2 and 3, and [2,1,3], where we start with 2 and permute 1 and 3.

2. Example 2:

   • Input: nums = [0,1]
   • Output: The permutations are [0,1] and [1,0].
   • These are straightforward as the array has only two elements, so swapping them gives the permutations.

3. Example 3:

   • Input: nums = [1]
   • Output: [[1]]
   • With only one element, the only "permutation" is the element itself.

Generation Techniques

• Backtracking Algorithm:

  • Recursively choose an element to be the next in the permutation sequence.
  • Use a temporary structure (like a list or a set) to keep track of what elements have been used.
  • Backtrack once you have considered all elements for the current sequence.

• Iterative Algorithms:

  • Techniques like Heap's Algorithm can be used to generate permutations by swapping elements systematically.

Given the constraints:

• Maximum array length is 6, so at most we are generating 720 permutations (6!).
• Elements are within a small integer range and are guaranteed unique, simplifying checks and swaps.

Each method suits different scenarios and complexities, especially when considering the reusability of elements and the cost of recursion or iteration control structures for higher factorial values.

Solutions

class Solution {
public:
    vector<vector<int>> generatePermutations(vector<int>& elements) {
        vector<vector<int>> result;
        vector<int> permutation;
        findPermutations(permutation, result, elements);
        return result;
    }
    
    void findPermutations(vector<int>& permutation, vector<vector<int>>& result, vector<int>& elements) {
        if (permutation.size() == elements.size()) {
            result.push_back(permutation);
            return;
        }
    
        for (int element : elements) {
            if (find(permutation.begin(), permutation.end(), element) == permutation.end()) {
                permutation.push_back(element);
                findPermutations(permutation, result, elements);
                permutation.pop_back();
            }
        }
    }
};