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],
- Starting with 1 - [1,2,3], [1,3,2]
- Then for 2 - [2,1,3], [2,3,1]
- 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.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.