Permutations medium

Problem Statement

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

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]]

Steps

1. Backtracking: We'll use backtracking to explore all possible permutations. Backtracking is a recursive algorithm that explores all possible combinations by making a choice, exploring the consequences, and then undoing that choice to explore other options.

2. Base Case: If the current permutation has the same length as the input array, we've found a complete permutation, so we add it to the result.

3. Recursive Step: For each element in the input array that hasn't been used in the current permutation, we:

   • Add the element to the current permutation.
   • Recursively call the function to explore permutations with the added element.
   • Remove the element from the current permutation (backtracking step) to explore other possibilities.

Explanation

The code uses a recursive helper function permuteHelper. It takes the input array nums, a vector currentPermutation to build the permutations, and a vector used to track which elements have already been used in the current permutation.

• Initially, permuteHelper is called with an empty currentPermutation and used vector filled with false (indicating no elements are used).

• In each recursive call, it iterates through nums. If an element is not used (!used[i]), it's added to currentPermutation, marked as used (used[i] = true), and the function recursively calls itself.

• After the recursive call returns, the element is removed from currentPermutation and marked as unused (used[i] = false), allowing exploration of other permutations.

• When currentPermutation's size equals nums's size, a complete permutation is found, and it's added to the result.

Code

#include <vector>
#include <algorithm>

class Solution {
public:
    std::vector<std::vector<int>> permute(std::vector<int>& nums) {
        std::vector<std::vector<int>> result;
        std::vector<int> currentPermutation;
        std::vector<bool> used(nums.size(), false);
        permuteHelper(nums, currentPermutation, used, result);
        return result;
    }

private:
    void permuteHelper(std::vector<int>& nums, std::vector<int>& currentPermutation, std::vector<bool>& used, std::vector<std::vector<int>>& result) {
        if (currentPermutation.size() == nums.size()) {
            result.push_back(currentPermutation);
            return;
        }

        for (int i = 0; i < nums.size(); ++i) {
            if (!used[i]) {
                used[i] = true;
                currentPermutation.push_back(nums[i]);
                permuteHelper(nums, currentPermutation, used, result);
                currentPermutation.pop_back(); // Backtrack: remove the last element
                used[i] = false; // Backtrack: mark the element as unused
            }
        }
    }
};

Complexity

• Time Complexity: O(n * n!), where n is the number of elements in the input array. There are n! permutations, and each permutation takes O(n) time to construct and add to the result.
• Space Complexity: O(n), primarily due to the recursive call stack and the currentPermutation vector. In the worst case, the depth of the recursion is n. The used vector also takes O(n) space.