46. Permutations

Description

This function generates all possible permutations of a given list of numbers.

Intuition

The problem can be solved using a depth-first search (DFS) approach by exploring all possible ways to arrange the elements of the list.

Approach

1. Define a helper function dfs that takes the starting index as an argument.
2. If the starting index is equal to the length of the list, add the current permutation to the result.
3. For each index from the start to the end of the list, swap the current element with the start element.
4. Recursively call dfs with the next starting index.
5. Swap back the elements to their original positions to explore other permutations.
6. Start the DFS from index 0.

Complexity

Time Complexity:

(O(N \times N!))

• There are (N!) permutations, and creating each permutation takes (O(N)) time.

Space Complexity:

(O(N!))

• The result list stores all permutations, and the recursion depth is (O(N)).

Code

C++

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

Python

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        result = []
        
        def dfs(start):
            if start == len(nums):
                result.append(nums[:])
                return
            
            for i in range(start, len(nums)):
                nums[start], nums[i] = nums[i], nums[start]
                dfs(start + 1)
                nums[start], nums[i] = nums[i], nums[start]
        
        dfs(0)
        return result

Java

class Solution {
    public List> permute(int[] nums) {
        List> result = new ArrayList<>();
        backtrack(result, new ArrayList<>(), nums);
        return result;
    }
    
    private void backtrack(List> result, List tempList, int[] nums) {
        if (tempList.size() == nums.length) {
            result.add(new ArrayList<>(tempList));
        } else {
            for (int i = 0; i < nums.length; i++) {
                if (tempList.contains(nums[i])) continue; // element already exists, skip
                tempList.add(nums[i]);
                backtrack(result, tempList, nums);
                tempList.remove(tempList.size() - 1);
            }
        }
    }
}

JavaScript

var permute = function(nums) {
    let result  = []
    function dfs (start, curResult) {
        if (start === nums.length) {
            result.push([...nums])
            return;
        }
        for(let i = start; i< nums.length; i++) {

            [nums[i], nums[start]] = [nums[start], nums[i]];

            dfs(start + 1, nums);
            
            [nums[i], nums[start]] = [nums[start], nums[i]];
        }
    }
    dfs(0, nums)
    return result
    
};