LeetCode Problem

Problem Description

Given an array nums of distinct integers, return all the possible permutations.

Examples

Input: [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Constraints

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

Follow-up

Approach to Solve

Use backtracking to generate all possible permutations.

Code Implementation

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def backtrack(path):
            if len(path) == len(nums):
                result.append(path[:])
                return
            for num in nums:
                if num not in path:
                    path.append(num)
                    backtrack(path)
                    path.pop()
        
        result = []
        backtrack([])
        return result

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

    private void backtrack(List<List<Integer>> result, List<Integer> tempList, int[] nums) {
        if (tempList.size() == nums.length) {
            result.add(new ArrayList<>(tempList));
            return;
        }
        for (int num : nums) {
            if (tempList.contains(num)) continue;  // element already exists, skip
            tempList.add(num);
            backtrack(result, tempList, nums);
            tempList.remove(tempList.size() - 1);
        }
    }

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

private:
    void backtrack(vector<vector<int>>& result, vector<int>& path, vector<int>& nums) {
        if (path.size() == nums.size()) {
            result.push_back(path);
            return;
        }
        for (int num : nums) {
            if (find(path.begin(), path.end(), num) != path.end()) continue;
            path.push_back(num);
            backtrack(result, path, nums);
            path.pop_back();
        }
    }

Explanation

This solution uses a backtracking approach to generate all possible permutations of the input array nums. Here's a detailed explanation of the algorithm:

Initialize an empty list result to store the resulting permutations.
Call the backtrack function with the initial parameters: result, an empty list path, and the input array nums.
In the backtrack function:
- If the size of path is equal to the length of nums, add a copy of path to result and return.
- Iterate through each number in nums:
  - If the number is already in path, skip it.
  - Add the number to path.
  - Recursively call backtrack with the updated parameters.
  - Remove the last added number from path (backtrack).
Return the result list containing all permutations of nums.

The time complexity is O(n!), where n is the length of nums, as we generate all possible permutations. The space complexity is O(n) for the recursion stack and to store each permutation.

Complexity

Time Complexity: O(n!)
Space Complexity: O(n)

LeetSolved

Permutations