Leetcode 46. Permutations

Problem Explanation:

This problem asks to return all possible permutations of a given list of unique integers. A permutation is an arrangement of all the members of a set into some sequence or order. For example, the permutations of [1,2,3] are [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

Let's take an example: Input: [1,2] Output: [[1,2], [2,1]] We can see that we have two numbers, we can take each as the initial and append the rest to it in a list. The result will be a list of two lists where each list represents a possible permutation.

Solution Approach:

We can use the Depth-First Search (DFS) algorithm to solve this problem. The approach would be to iterate through the list of numbers and for each number, run dfs to get all the permutations that can be formed with this number as the first number, and then append the resultant permutations to the list of answers.

We will use a boolean array 'used' of the same length as the input array to keep track of the elements that have already been used in the current permutation.

Here is how it would go about for an input of [1,2,3],

1. Starting with 1 - [1,2,3], [1,3,2]
2. Then for 2 - [2,1,3], [2,3,1]
3. Lastly for 3 - [3,1,2], [3,2,1]

Python Solution:

1
2python
3class Solution:
4    def permute(self, nums):
5        def dfs(nums, path, used, res):
6            if len(path) == len(nums):
7                res.append(path)
8                return
9            for i in range(len(nums)):
10                if not used[i]:
11                    used[i] = True
12                    dfs(nums, path + [nums[i]], used, res)
13                    used[i] = False
14
15        res = []
16        used = [False for _ in range(len(nums))]
17        dfs(nums, [], used, res)
18        return res

Java Solution:

1
2java
3class Solution {
4    private void dfs(int[] nums, ArrayList<Integer> path, boolean[] used, List<List<Integer>> res) {
5        if (path.size() == nums.length) {
6            res.add(new ArrayList<>(path));
7            return;
8        }
9
10        for (int i = 0; i < nums.length; ++i) {
11            if (!used[i]) {
12                used[i] = true;
13                path.add(nums[i]);
14                dfs(nums, path, used, res);
15                used[i] = false;
16                path.remove(path.size() - 1);
17            }
18        }
19    }
20
21    public List<List<Integer>> permute(int[] nums) {
22        List<List<Integer>> res = new ArrayList<>();
23        dfs(nums, new ArrayList<>(), new boolean[nums.length], res);
24        return res;
25    }
26}

Javascript Solution:

1
2javascript
3var permute = function(nums) {
4    let res = [];
5    dfs(nums, [], []);
6    function dfs(nums, path, used) {
7        if(path.length == nums.length) {
8            res.push([...path]);
9            return;
10        }
11
12        for(let i = 0; i < nums.length; i++) {
13            if(used[i]) continue;
14            used[i] = true;
15            path.push(nums[i]);
16            dfs(nums, path, used);
17            used[i] = false;
18            path.pop();
19        }
20    }
21    return res;
22};

C++ Solution:

1
2cpp
3class Solution {
4public:
5    vector<vector<int>> permute(vector<int>& nums) {
6        vector<vector<int>> res;
7        dfs(nums, vector<int> {}, res);
8        return res;
9    }
10
11private:
12    void dfs(vector<int>& nums, vector<int> path, vector<vector<int>>& res) {
13    if (path.size() == nums.size()) {
14        res.push_back(path);
15        return;
16    }
17
18    for (auto x : nums) {
19        if (std::find(path.begin(), path.end(), x) != path.end())
20            continue;
21        
22        path.push_back(x);
23        dfs(nums, path, res);
24        path.pop_back();
25        }
26    }
27};

C# Solution:

1
2csharp
3public class Solution {
4    private void Dfs(int[] nums, IList<int> path, bool[] used, IList<IList<int>> res) {
5        if (path.Count == nums.Length) {
6            res.Add(new List<int>(path));
7            return;
8        }
9
10        for (int i = 0; i < nums.Length; ++i) {
11            if (!used[i]) {
12                used[i] = true;
13                path.Add(nums[i]);
14                Dfs(nums, path, used, res);
15                used[i] = false;
16                path.RemoveAt(path.Count - 1);
17            }
18        }
19    }
20
21    public IList<IList<int>> Permute(int[] nums) {
22        IList<IList<int>> res = new List<IList<int>>();
23        Dfs(nums, new List<int>(), new bool[nums.Length], res);
24        return res;
25    }
26}

Detailed Breakdown and Explanation:

Let's take a closer look at the Python solution for a better understanding.

1
2python
3class Solution:
4    def permute(self, nums):
5        def dfs(nums, path, used, res):    # Nested helper function
6            if len(path) == len(nums):     
7                res.append(path)            # Add current path to result if it uses all numbers
8                return
9            for i in range(len(nums)):
10                if not used[i]:             # Only proceed if number hasn't been used
11                    used[i] = True          
12                    dfs(nums, path + [nums[i]], used, res)    # Recursive call with current number added to path
13                    used[i] = False           # Reset current number to unused
14
15        res = []
16        used = [False for _ in range(len(nums))]   # Initialize used array
17        dfs(nums, [], used, res)
18        return res

At the highest level, the function initializes a result array res and a boolean array used to keep track of which numbers have been used. It then calls the helper function dfs with the list of numbers, an empty path, the used array, and the result array.

The dfs function checks if the current path uses all numbers. If it does, it adds this path to the result array. If it doesn't, it iterates over all numbers. For each number, it checks if it can be added to the current path, i.e., if it hasn't been used yet. If it can be added, it sets the corresponding boolean to True, adds the number to the path, and makes a recursive call to dfs with the updated parameters.

After the recursive call, it resets the boolean for the current number to false, effectively "backtracking" and allowing the number to be used in other future paths.

The other solutions in JavaScript, Java, C++, and C# follow a similar approach, differing primarily in the specifics of the syntax and standard library methods.

These implementations take advantage of recursion and the depth-first search algorithm to thoroughly explore all possible permutations, making them an efficient and effective approach to solving this problem.