47. Permutations II – Leetcode Solutions

June 15, 2024

Table of Contents

Description:

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

Examples:

Example 1:

Input: nums = [1,1,2]
Output:
[[1,1,2],
 [1,2,1],
 [2,1,1]]
 
Example 2:

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

Solution in Python:

To solve the problem of generating all unique permutations of an array of integers that might contain duplicates, we can use a backtracking approach with additional logic to handle duplicates.

Python

from typing import List

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        def backtrack(nums, path, used, res):
            if len(path) == len(nums):
                res.append(path[:])
                return
            
            for i in range(len(nums)):
                # Skip used elements or duplicates
                if used[i] or (i > 0 and nums[i] == nums[i - 1] and not used[i - 1]):
                    continue
                
                # Mark this element as used
                used[i] = True
                path.append(nums[i])
                
                # Recurse with the element included in the path
                backtrack(nums, path, used, res)
                
                # Backtrack: remove the element from the path and mark it as not used
                path.pop()
                used[i] = False
        
        # Sort the array to handle duplicates easily
        nums.sort()
        res = []
        used = [False] * len(nums)
        
        # Start backtracking
        backtrack(nums, [], used, res)
        return res

Explanation:

Initialization:
- We define a class Solution with a method permuteUnique that takes an array of integers nums as input and returns a list of lists of integers, where each list is a unique permutation of the input array.
Backtracking Function:
- We define a helper function backtrack that takes the original array nums, a list path to build the current permutation, a list used to keep track of used elements, and the res list to store all unique permutations.
- If the length of path equals the length of nums, it means we have generated a complete permutation. We then add a copy of path to the res list.
- For each index in the array, we:
  - Skip elements that are already used or duplicates (i.e., elements that are the same as the previous element and the previous element was not used).
  - Add the current element to path and mark it as used.
  - Recursively call backtrack to continue generating permutations with the current element included.
  - Remove the last element added to path and mark it as not used to backtrack and explore the next possibility.
Sorting and Initial Call:
- We sort the array nums to handle duplicates easily.
- We initialize the res list to store results and the used list to keep track of used elements.
- We start the backtracking process by calling backtrack(nums, [], used, res).
Example Usage:
- We test the permuteUnique method with different input arrays to ensure it generates the correct unique permutations.

By sorting the array and using a used list to track which elements are included in the current permutation, we can efficiently generate all unique permutations. The backtracking approach ensures that we explore all possibilities while handling duplicates appropriately.

Solution in Javascript:

JavaScript

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function(nums) {
    // Function to perform backtracking
    const backtrack = (nums, path, used, res) => {
        // If the path length is equal to nums length, we have a complete permutation
        if (path.length === nums.length) {
            res.push([...path]); // Add a copy of the current path to results
            return;
        }
        
        for (let i = 0; i < nums.length; i++) {
            // Skip used elements or duplicates
            if (used[i] || (i > 0 && nums[i] === nums[i - 1] && !used[i - 1])) continue;
            
            // Mark this element as used
            used[i] = true;
            path.push(nums[i]);
            
            // Recurse with the element included in the path
            backtrack(nums, path, used, res);
            
            // Backtrack: remove the element from the path and mark it as not used
            path.pop();
            used[i] = false;
        }
    };

    nums.sort((a, b) => a - b); // Sort the array to handle duplicates
    const res = [];
    const used = Array(nums.length).fill(false);
    
    // Start backtracking
    backtrack(nums, [], used, res);
    return res;
};

Solution in Java:

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);  // Sort the array to handle duplicates
        boolean[] used = new boolean[nums.length];  // Track used elements
        backtrack(nums, new ArrayList<>(), used, res);
        return res;
    }

    private void backtrack(int[] nums, List<Integer> path, boolean[] used, List<List<Integer>> res) {
        // If the path length is equal to nums length, we have a complete permutation
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));  // Add a copy of the current path to results
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            // Skip used elements or duplicates
            if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) continue;

            // Mark this element as used
            used[i] = true;
            path.add(nums[i]);

            // Recurse with the element included in the path
            backtrack(nums, path, used, res);

            // Backtrack: remove the element from the path and mark it as not used
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }

    
}

Solution in C#:

C#

using System;
using System.Collections.Generic;

public class Solution {
    public IList<IList<int>> PermuteUnique(int[] nums) {
        IList<IList<int>> res = new List<IList<int>>();
        Array.Sort(nums); // Sort the array to handle duplicates
        bool[] used = new bool[nums.Length]; // Track used elements
        Backtrack(nums, new List<int>(), used, res);
        return res;
    }

    private void Backtrack(int[] nums, List<int> path, bool[] used, IList<IList<int>> res) {
        // If the path length is equal to nums length, we have a complete permutation
        if (path.Count == nums.Length) {
            res.Add(new List<int>(path)); // Add a copy of the current path to results
            return;
        }

        for (int i = 0; i < nums.Length; i++) {
            // Skip used elements or duplicates
            if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) continue;

            // Mark this element as used
            used[i] = true;
            path.Add(nums[i]);

            // Recurse with the element included in the path
            Backtrack(nums, path, used, res);

            // Backtrack: remove the element from the path and mark it as not used
            path.RemoveAt(path.Count - 1);
            used[i] = false;
        }
    }

   
}

47. Permutations II – Leetcode Solutions

Description:

Solution in Python:

Solution in Javascript:

Solution in Java:

Solution in C#:

Popular

218. The Skyline Problem – Leetcode Solutions

392. Is Subsequence – Leetcode Solutions

343. Integer Break – Leetcode Solutions

142. Linked List Cycle II – Leetcode Solutions

154. Find Minimum in Rotated Sorted Array II – Leetcode Solutions

Pascal’s Triangle II (Task 119 Array) – Solutions

143. Reorder List – Leetcode Solutions

47. Permutations II – Leetcode Solutions

Description:

Solution in Python:

Solution in Javascript:

Solution in Java:

Solution in C#:

Related Post

Popular