Print all permutations of a string/array

Dec 18, 2024 • 4 mins read

Dhaval Trivedi

Co-founder, Airtribe

Problem Overview

The problem titled "Permutations", found on LeetCode, delves into the concepts of recursion and backtracking. The task requires generating all possible permutations of a given list of distinct integers. It's a classic problem that encapsulates the beauty of combinatorial algorithms, pivotal in numerous computational fields.

Understanding the Problem

Given an array of distinct integers, the objective is to return all possible permutations of the array elements. A permutation of a set is a re-arrangement of its elements. For an array of size n, you can expect n! (n factorial) permutations.

For example, if the input array is [1, 2, 3], the possible permutations are:

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

Key DSA Concepts and Theory

The concepts necessary for solving this problem are:

Recursion

Recursion is a technique wherein a function makes one or more calls to itself with a modified input. It's particularly useful for problems like permutations, where we need to explore possible configurations of an input.

Backtracking

Backtracking is an extension of recursion. It systematically explores all possible configurations of a problem and abandons those which clearly cannot yield a solution (pruning). This approach is ideal for permutations as it involves exploring possibilities and reversing (backtracking) when needed.

Factorial Growth

The number of permutations of a list grows factorially with the size of the list. For an input list of length n, there are n! permutations. Factorial growth is very steep and quickly leads to large computation needs as n increases.

Solution Approach

To generate all permutations of the input list, we can follow these steps:

Recursive Function: Develop a recursive function to build permutations from partial permutations by:
- Choosing an element as the starting element.
- Recursively calculating permutations for the rest of the elements.
Backtracking: Revert any choice once tested — this helps in exploring other potential configurations without needing vector maintenance.

C++ Solution

#include <vector>
using namespace std;

class Solution {
public:
    void permuteHelper(vector<int>& nums, vector<vector<int>>& result, int start) {
        if (start >= nums.size()) {
            result.push_back(nums);
            return;
        }
        for (int i = start; i < nums.size(); ++i) {
            swap(nums[start], nums[i]);
            permuteHelper(nums, result, start + 1);
            swap(nums[start], nums[i]); // backtrack
        }
    }
    
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> result;
        permuteHelper(nums, result, 0);
        return result;
    }
};

Java Solution

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        permuteHelper(nums, 0, result);
        return result;
    }
    
    private void permuteHelper(int[] nums, int start, List<List<Integer>> result) {
        if (start >= nums.length) {
            List<Integer> current = new ArrayList<>();
            for (int num : nums) current.add(num);
            result.add(current);
            return;
        }
        for (int i = start; i < nums.length; i++) {
            swap(nums, start, i);
            permuteHelper(nums, start + 1, result);
            swap(nums, start, i); // backtrack
        }
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

Time and Space Complexity Analysis

Time Complexity

The time complexity of generating permutations is O(n * n!), where n is the length of the input list. This accounts for n! permutations each requiring copying n elements.

Space Complexity

The space complexity is O(n!) for holding all permutations, with O(n) additional space for recursion call stack.

Common Mistakes to Avoid

Modifying List Without Backtracking: Ensure that modifications done to the list during each recursive call are undone (backtracked) to explore the next permutation correctly.
Expecting Sublinear Time: Recognize that permutation generation inherently needs O(n!) operations due to its combinatorial nature.

Additional Resources and References

This guide aims to equip you with the understanding of permutations problem-solving using recursion and backtracking, pivotal concepts for algorithm design and combinatorial problems.