Permutations

Problem

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

Solution Approach

Refer Code for self explanation and algorithm.

Expected Time complexity: $O(n!)$

Click - to see solution code

C++

class Solution {
   public:
    vector<vector<int> > permute(vector<int> &num) {
        vector<vector<int> > result;

        permuteRecursive(num, 0, result);
        return result;
    }

    void permuteRecursive(vector<int> &num, int begin,
                          vector<vector<int>> &result) {
        if (begin >= num.size()) {
            result.push_back(num);
            return;
        }

        for (int i = begin; i < num.size(); i++) {
            swap(num[begin], num[i]);
            permuteRecursive(num, begin + 1, result);
            swap(num[begin], num[i]);
        }
    }
};