Imprima todas las permutaciones posibles de una array con duplicados usando Backtracking

Dada una array nums[] de tamaño N , la tarea es imprimir todas las posibles permutaciones distintas de la array nums[] ( incluidos los duplicados ).

Entrada: nums[] = { 1, 2, 2 }
Salida: 
1 2 1
2 1 2
2 2 1

Entrada: nums[] = { 1, 1 }
Salida: 1 1

Enfoque: siga los pasos a continuación para resolver el problema

1. Atraviesa la array .
2. Generar permutaciones de una array .
3. Establezca un orden de selección entre los elementos duplicados.
4. Si i > 0 && nums[i] == nums[i – 1]: agregue nums[i] en la permutación actual solo si se ha agregado nums[i – 1] en la permutación, es decir, visited[i – 1] es cierto _
5. De lo contrario, continúa .
6. Usando este enfoque, imprima las distintas permutaciones generadas.

Consulte este Árbol de recurrencia para comprender los detalles de implementación del código.

A continuación se muestra la implementación del enfoque anterior:

// C++ Program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to fill the vector curr
// while maintaining the indices visited
// in the array num
void backtrack(vector<int>& nums,
               vector<int>& curr,
               vector<vector<int> >& ans,
               vector<bool>& visited)
{
 
    // If current permutation is complete
    if ((int)curr.size() == (int)nums.size()) {
        ans.push_back(curr);
    }
 
    // Traverse the input vector
    for (int i = 0; i < (int)nums.size();
         i++) {
 
        // If index is already visited
        if (visited[i])
            continue;
 
        // If the number is duplicate
        if (i > 0 and nums[i] == nums[i - 1]
            and !visited[i - 1])
            continue;
 
        // Set visited[i] flag as true
        visited[i] = true;
 
        // Push nums[i] to current vector
        curr.push_back(nums[i]);
 
        // Recursive function call
        backtrack(nums, curr,
                  ans, visited);
 
        // Backtrack to the previous
        // state by unsetting visited[i]
        visited[i] = false;
 
        // Pop nums[i] and place at
        // the back of the vector
        curr.pop_back();
    }
}
 
// Function to pre-process the vector num
vector<vector<int> > permuteDuplicates(
    vector<int>& nums)
{
    // Sort the array
    sort(nums.begin(), nums.end());
 
    // Stores distinct permutations
    vector<vector<int> > ans;
 
    vector<bool> visited(
        (int)nums.size(), false);
 
    // Store the current permutation
    vector<int> curr;
 
    // Find the distinct permutations of num
    backtrack(nums, curr, ans, visited);
 
    return ans;
}
 
// Function call to print all distinct
// permutations of the vector nums
void getDistinctPermutations(vector<int> nums)
{
    // Find the distinct permutations
    vector<vector<int> > ans
        = permuteDuplicates(nums);
 
    // Traverse every row
    for (int i = 0; i < (int)ans.size();
         i++) {
 
        // Traverse every column
        for (int j = 0; j < (int)ans[i].size();
             j++) {
 
            cout << ans[i][j] << " ";
        }
 
        cout << '\n';
    }
}
 
// Driver Code
int main()
{
    // Input
    vector<int> nums = { 1, 2, 2 };
 
    // Function call to print
    // all distinct permutations
    getDistinctPermutations(nums);
 
    return 0;
}

// Java Program to implement
// the above approach
import java.io.*;
import java.util.*;
class GFG {
 
  static ArrayList<Integer> nums = new ArrayList<Integer>();
  static ArrayList<Integer> curr = new ArrayList<Integer>();
  static ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
  static ArrayList<Boolean> visited = new ArrayList<Boolean>();
 
  // Function to fill the vector curr
  // while maintaining the indices visited
  // in the array num
  static void backtrack()
  {
 
    // If current permutation is complete
    if (curr.size() == nums.size())
    {
      ans.add(curr);
      for(int i = 0; i < curr.size(); i++)
      {
        System.out.print(curr.get(i) +" ");
      }
      System.out.println();
    }
 
    // Traverse the input vector
    for (int i = 0; i < (int)nums.size();
         i++)
    {
 
      // If index is already visited
      if (visited.get(i))
        continue;
 
      // If the number is duplicate
      if (i > 0 && (nums.get(i) == nums.get(i - 1)) && !visited.get(i - 1))
        continue;
 
      // Set visited[i] flag as true
      visited.set(i, true);
 
      // Push nums[i] to current vector
      curr.add(nums.get(i));
 
      // Recursive function call
      backtrack();
 
      // Backtrack to the previous
      // state by unsetting visited[i]
      visited.set(i, false);
 
      // Pop nums[i] and place at
      // the back of the vector
      curr.remove(curr.size() - 1);
    }
  }
  // Function to pre-process the vector num
  static ArrayList<ArrayList<Integer>> permuteDuplicates()
  {
    // Sort the array
    Collections.sort(nums);
 
    for(int i = 0; i < nums.size(); i++)
    {
      visited.add(false);
    }
 
    // Find the distinct permutations of num
    backtrack();
 
    return ans;
 
  }
 
  // Function call to print all distinct
  // permutations of the vector nums
 
  static void getDistinctPermutations()
  {
    ans = permuteDuplicates();
 
 
  }
 
  // Driver code
  public static void main (String[] args)
  {
 
    // Input
    nums.add(1);
    nums.add(2);
    nums.add(2);
 
    // Function call to print
    // all distinct permutations
    getDistinctPermutations();
  }
}
 
// This code is contributed by avanitrachhadiya2155

# Python3 Program to implement
# the above approach
 
# Function to fill the vector curr
# while maintaining the indices visited
# in the array num
def backtrack():
    global ans, curr, visited, nums
     
    # If current permutation is complete
    # print(ans)
    if (len(curr) == len(nums)):
        print(*curr)
 
    # Traverse the input vector
    for i in range(len(nums)):
 
        # If index is already visited
        if (visited[i]):
            continue
 
        # If the number is duplicate
        if (i > 0 and nums[i] == nums[i - 1] and visited[i - 1]==False):
            continue
 
        # Set visited[i] flag as true
        visited[i] = True
 
        # Push nums[i] to current vector
        curr.append(nums[i])
 
        # Recursive function call
        backtrack()
 
        # Backtrack to the previous
        # state by unsetting visited[i]
        visited[i] = False
 
        # Pop nums[i] and place at
        # the back of the vector
        del curr[-1]
 
# Function to pre-process the vector num
def permuteDuplicates(nums):
    global ans, visited, curr
    nums = sorted(nums)
 
    # Find the distinct permutations of num
    backtrack()
    return ans
 
# Function call to print all distinct
# permutations of the vector nums
def getDistinctPermutations(nums):
    global ans, curr, visited
     
    # Find the distinct permutations
    ans = permuteDuplicates(nums)
 
# Driver Code
if __name__ == '__main__':
    visited = [False]*(5)
    ans,curr = [], []
    nums = [1, 2, 2]
 
    # Function call to print
    # all distinct permutations
    getDistinctPermutations(nums)
 
    # This code is contributed by mohit kumar 29.

// C# Program to implement
// the above approach
using System;
using System.Collections.Generic;
 
public class GFG{
 
  static List<int> nums = new List<int>();
  static List<int> curr = new List<int>();
  static List<List<int>> ans = new List<List<int>>();
  static List<bool> visited = new List<bool>();
 
  // Function to fill the vector curr
  // while maintaining the indices visited
  // in the array num
  static void backtrack()
  {
 
    // If current permutation is complete
    if (curr.Count == nums.Count)
    {
      ans.Add(curr);
      for(int i = 0; i < curr.Count; i++)
      {
        Console.Write(curr[i] +" ");
      }
      Console.WriteLine();
    }
 
    // Traverse the input vector
    for (int i = 0; i < (int)nums.Count;
         i++)
    {
 
      // If index is already visited
      if (visited[i])
        continue;
 
      // If the number is duplicate
      if (i > 0 && (nums[i] == nums[i-1]) && !visited[i-1])
        continue;
 
      // Set visited[i] flag as true
      visited[i] = true;
 
      // Push nums[i] to current vector
      curr.Add(nums[i]);
 
      // Recursive function call
      backtrack();
 
      // Backtrack to the previous
      // state by unsetting visited[i]
      visited[i] = false;
 
      // Pop nums[i] and place at
      // the back of the vector
      curr.RemoveAt(curr.Count - 1);
    }
  }
 
  // Function to pre-process the vector num
  static List<List<int>> permuteDuplicates()
  {
    // Sort the array
    nums.Sort();
 
    for(int i = 0; i < nums.Count; i++)
    {
      visited.Add(false);
    }
 
    // Find the distinct permutations of num
    backtrack();
 
    return ans;
 
  }
 
  // Function call to print all distinct
  // permutations of the vector nums
 
  static void getDistinctPermutations()
  {
    ans = permuteDuplicates();
 
 
  }
 
  // Driver code
  static public void Main (){
 
    // Input
    nums.Add(1);
    nums.Add(2);
    nums.Add(2);
 
    // Function call to print
    // all distinct permutations
    getDistinctPermutations();
 
  }
}
 
// This code is contributed by rag2127

<script>
 
// JavaScript Program to implement
// the above approach
 
let nums = [];
let curr = [];
let ans = [];
let visited = [];
 
// Function to fill the vector curr
  // while maintaining the indices visited
  // in the array num
function backtrack()
{
    // If current permutation is complete
    if (curr.length == nums.length)
    {
      ans.push(curr);
      for(let i = 0; i < curr.length; i++)
      {
        document.write(curr[i] +" ");
      }
      document.write("<br>");
    }
  
    // Traverse the input vector
    for (let i = 0; i < nums.length;
         i++)
    {
  
      // If index is already visited
      if (visited[i])
        continue;
  
      // If the number is duplicate
      if (i > 0 && (nums[i] == nums[i - 1]) && !visited[i - 1])
        continue;
  
      // Set visited[i] flag as true
      visited[i] = true;
  
      // Push nums[i] to current vector
      curr.push(nums[i]);
  
      // Recursive function call
      backtrack();
  
      // Backtrack to the previous
      // state by unsetting visited[i]
      visited[i] = false;
  
      // Pop nums[i] and place at
      // the back of the vector
      curr.pop();
    }
}
 
 // Function to pre-process the vector num
function permuteDuplicates()
{
    // Sort the array
    (nums).sort(function(a,b){return a-b});
  
    for(let i = 0; i < nums.length; i++)
    {
      visited.push(false);
    }
  
    // Find the distinct permutations of num
    backtrack();
  
    return ans;
}
 
// Function call to print all distinct
  // permutations of the vector nums
function getDistinctPermutations()
{
    ans = permuteDuplicates();
}
 
 // Driver code
// Input
nums.push(1);
nums.push(2);
nums.push(2);
 
// Function call to print
// all distinct permutations
getDistinctPermutations();
 
 
// This code is contributed by unknown2108
 
</script>

1 2 2 
2 1 2 
2 2 1

Complejidad temporal: O(N! * N)
Espacio auxiliar : O(N! * N)