Leetcode 47. Permutations II

Problem Explanation

Given a collection of numbers which may have duplicates, the problem requires you to create all possible unique permutations of the numbers.

For instance, if we are given an input array [1,1,2], output will be [[1,1,2],[1,2,1],[2,1,1]] which are all unique permutations that we can get from array [1,1,2].

Solution Approach

This solution uses Depth-First Search (DFS) algorithm. The DFS is a traversal algorithm used to traverse through a tree or a graph. It is called depth-first search because it starts from the root (assuming as an entry point in the graph), then starts visiting any one of the branch as deep as it can get. In this way, it visits all the nodes depth-wise.

Start off by sorting the array, this helps in avoiding duplicate permutations. Initiate a DFS search with empty path, in each DFS recurse, visit every number in the array, if it was already visited, continue to next number. If it was not visited before or if it equals to the previous number and the previous number is not visited too, then continue to next number, to avoid duplicate permutations. If it was not visited before and doesn't equal to previous number, or it equals to previous number and the previous number was visited, then add it to the path and do a DFS with this new path. Continue this until all numbers are visited.

Let's run this algorithm with the example [1,1,2].

1. Initiate dfs with empty path, visit 1st number 1, it was not visited, so add to path and initiate new dfs. Now path = [1].
2. In 2nd dfs, visit 1st number 1, it's same as previous number and previous is unvisited, so continue to next number, now visit 2, it was not visited, so add to path and initiate new dfs. Now path = [1,2].
3. In 3rd dfs, only one unvisited number left 1, so add to path and initiate new dfs. Now path = [1,2,1].
4. In 4th dfs, no more unvisited numbers left, so add the path to answer. Now ans = [[1,2,1]].
5. Backtrack to 3rd dfs, remove last number from path, there are no more unvisited numbers, so return. Now path = [1,2].
6. Backtrack to 2nd dfs, remove last number from path, now visit 1, it's same as previous number but previous is now visited, so add to path and initiate new dfs. Now path = [1,1].
7. In 3rd dfs, only one unvisited number left 2, so add to path and initiate new dfs. Now path = [1,1,2].
8. In 4th dfs, no more unvisited numbers left, so add the path to answer. Now ans = [[1,2,1],[1,1,2]].
9. Backtrack until the first dfs and repeat the process with the next numbers. We will get ans = [[1,2,1],[1,1,2],[2,1,1]].

Now, let's see how you can implement this algorithm in Python, Java, JavaScript, C++ and C#.

Python Solution

1
2python
3class Solution:
4    def permuteUnique(self, nums):
5        def dfs(nums, path, res):
6            if not nums:
7                res.append(path)
8                return 
9            for i in range(len(nums)):
10                if i > 0 and nums[i] == nums[i - 1]:
11                  continue;
12                dfs(nums[:i] + nums[i+1:], path + [nums[i]], res)
13        res = []
14        nums.sort()
15        dfs(nums, [], res)
16        return res

Java Solution

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

JavaScript Solution

1
2javascript
3var permuteUnique = function(nums) {
4    let res = [];
5    nums.sort((a, b) => a - b);
6    dfs(nums, [], Array(nums.length).fill(false), res);
7    return res;
8};
9
10function dfs(nums, path, visited, res) {
11    if(path.length == nums.length) {
12        res.push(Array.from(path));
13        return;
14    }
15    for(let i = 0; i < nums.length; i++) {
16        if(visited[i]) continue;
17        if(i > 0 && nums[i] == nums[i - 1] && !visited[i-1]) continue;
18        path.push(nums[i]);
19        visited[i] = true;
20        dfs(nums, path, visited, res);
21        visited[i] = false;
22        path.pop();
23    }
24}

C++ Solution

1
2cpp
3class Solution {
4public:
5    vector<vector<int>> permuteUnique(vector<int>& nums) {
6        sort(nums.begin(), nums.end());
7        vector<vector<int>> res;
8        dfs(nums, vector<int>(), vector<bool>(nums.size(), false), res);
9        return res;
10    }
11
12private:
13    void dfs(vector<int>& nums, vector<int> path, vector<bool> visited, vector<vector<int>>& res) {
14        if (path.size() == nums.size()) {
15            res.push_back(path);
16            return;
17        }
18        for (int i=0; i<nums.size(); i++) {
19            if (visited[i] || (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1])) {
20                continue;
21            }
22            path.push_back(nums[i]);
23            visited[i] = true;
24            dfs(nums, path, visited, res);
25            path.pop_back();
26            visited[i] = false;
27        }
28    }
29};

C# Solution

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

These solutions use the Depth-First Search (DFS) algorithm to generate unique permutations of numbers. Each solution follows the sequence of sorting the input number array, then repeatedly visiting unvisited numbers in the array. If it encounters a number that's the same as the previous, it checks if the previous number was visited. If not, it continues to the next number to avoid duplicate permutations. If it's a new number or the previous number was visited, it adds the new number to the path and initiates a new DFS.

The Python solution defines a class and implements the dfs method. It checks each number and if it's the same as the previous number in the sorted array, it continues to avoid duplicates. The Java solution operates similarly, but with explicit handling of visited nodes. The JavaScript solution adds a visited array to keep track of which numbers have been used in the current path, preventing the same number from being used in a permutation multiple times. The C++ solution uses vectors to store the paths and results. As paths are completed, they are added to the vector of results. The C# solution also operates similarly, in the context of a Solution class.

These solutions have a time complexity of O(N!) due to having to generate all possible permutations. N is the size of the input array. Each permutation is built incrementally by visiting each number in the array and ensuring all permutations are generated with and without the chosen number until all the numbers are visited.