Imprime todas las combinaciones generadas por caracteres de una string numérica que no exceda N

Dada una string numérica S de longitud M y un número entero N , la tarea es encontrar todas las combinaciones distintas de S ( repeticiones permitidas ) que sean como máximo N.

Ejemplos:

Entrada: S = “124”, N = 100
Salida: 1, 11, 12, 14, 2, 21, 22, 24, 4, 41, 42, 44
Explicación: Combinaciones “111”, “112”, “122” , «124», «412» son mayores que 100. Por lo tanto, estas combinaciones se excluyen de la salida.

Entrada: S = “345”, N = 400
Salida: 3, 33, 333, 334, 335, 34, 343, 344, 345, 35, 353, 354, 355, 4, 43, 44, 45, 5, 53 , 54, 55

Enfoque: la idea es generar todos los números posibles usando Backtracking y luego imprimir esos números que no excedan N . Siga los pasos a continuación para resolver el problema:

• Inicialice un Conjunto de strings, digamos combinaciones[], para almacenar todas las combinaciones distintas de S que numéricamente no excedan N .
• Inicialice una string ans para almacenar la combinación actual de números posibles de S .
• Declare una función generateCombinations() para generar todas las combinaciones requeridas cuyos valores sean menores que el valor N dado y la función se define como:
  • Recorra la string S sobre el rango [0, M] usando la variable i y haga lo siguiente:
    • Empuje el carácter actual S[i] a ans y convierta la string actual ans al número y guárdelo en x .
    • Si x es menor o igual que N , inserte la string ans en combinaciones[] y llame recursivamente a la función generarCombinaciones() .
  • Vuelva a su estado anterior eliminando el i- ^ésimo carácter de ans .
• Después de completar los pasos anteriores, imprima el conjunto de todas las strings almacenadas en combinaciones[] .

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Store the current sequence of s
string combination;
 
// Store the all the required sequences
set<string> combinations;
 
// Function to print all sequences of S
// satisfying the required condition
void printSequences(
    set<string> combinations)
{
    // Print all strings in the set
    for (string s : combinations) {
        cout << s << ' ';
    }
}
 
// Function to generate all sequences
// of string S that are at most N
void generateCombinations(string& s, int n)
{
 
    // Iterate over string s
    for (int i = 0; i < s.size(); i++) {
 
        // Push ith character to combination
        combination.push_back(s[i]);
 
        // Convert the string to number
        long x = stol(combination);
 
        // Check if the condition is true
        if (x <= n) {
 
            // Push the current string to
            // the final set of sequences
            combinations.insert(combination);
 
            // Recursively call function
            generateCombinations(s, n);
        }
 
        // Backtrack to its previous state
        combination.pop_back();
    }
}
 
// Driver Code
int main()
{
    string S = "124";
    int N = 100;
 
    // Function Call
    generateCombinations(S, N);
 
    // Print required sequences
    printSequences(combinations);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Store the current sequence of s
static String combination = "";
 
// Store the all the required sequences
static HashSet<String> combinations = new LinkedHashSet<String>();
 
// Function to print all sequences of S
// satisfying the required condition
static void printSequences(
    HashSet<String> combinations)
{
     
    // Print all Strings in the set
    for(String s : combinations)
    {
        System.out.print(s + " ");
    }
}
 
// Function to generate all sequences
// of String S that are at most N
static void generateCombinations(String s, int n)
{
     
    // Iterate over String s
    for(int i = 0; i < s.length(); i++)
    {
         
        // Push ith character to combination
        combination += (s.charAt(i));
 
        // Convert the String to number
        long x = Integer.valueOf(combination);
 
        // Check if the condition is true
        if (x <= n)
        {
             
            // Push the current String to
            // the final set of sequences
            combinations.add(combination);
 
            // Recursively call function
            generateCombinations(s, n);
        }
 
        // Backtrack to its previous state
        combination = combination.substring(
            0, combination.length() - 1);
    }
}
 
// Driver Code
public static void main(String[] args)
{
    String S = "124";
    int N = 100;
     
    // Function Call
    generateCombinations(S, N);
 
    // Print required sequences
    printSequences(combinations);
}
}
 
// This code is contributed by Amit Katiyar

# Python3 program for the above approach
 
# Store the current sequence of s
combination = "";
 
# Store the all the required sequences
combinations = [];
 
# Function to print all sequences of S
# satisfying the required condition
def printSequences(combinations) :
     
    # Print all strings in the set
    for s in (combinations) :
        print(s, end = ' ');
  
# Function to generate all sequences
# of string S that are at most N
def generateCombinations(s, n) :   
    global combination;
 
    # Iterate over string s
    for i in range(len(s)) :
 
        # Push ith character to combination
        combination += s[i];
 
        # Convert the string to number
        x = int(combination);
 
        # Check if the condition is true
        if (x <= n) :
 
            # Push the current string to
            # the final set of sequences
            combinations.append(combination);
 
            # Recursively call function
            generateCombinations(s, n);
 
        # Backtrack to its previous state
        combination = combination[:-1];
 
# Driver Code
if __name__ == "__main__" :
 
    S = "124";
    N = 100;
 
    # Function Call
    generateCombinations(S, N);
 
    # Print required sequences
    printSequences(combinations);
 
    # This code is contributed by AnkThon

// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
 
// Store the current sequence of s
static String combination = "";
 
// Store the all the required sequences
static SortedSet<String> combinations = new SortedSet<String>();
 
// Function to print all sequences of S
// satisfying the required condition
static void printSequences(
    SortedSet<String> combinations)
{
     
    // Print all Strings in the set
    foreach(String s in combinations)
    {
        Console.Write(s + " ");
    }
}
 
// Function to generate all sequences
// of String S that are at most N
static void generateCombinations(String s, int n)
{
     
    // Iterate over String s
    for(int i = 0; i < s.Length; i++)
    {
         
        // Push ith character to combination
        combination += (s[i]);
 
        // Convert the String to number
        long x = Int32.Parse(combination);
 
        // Check if the condition is true
        if (x <= n)
        {
             
            // Push the current String to
            // the readonly set of sequences
            combinations.Add(combination);
 
            // Recursively call function
            generateCombinations(s, n);
        }
 
        // Backtrack to its previous state
        combination = combination.Substring(
            0, combination.Length - 1);
    }
}
 
// Driver Code
public static void Main(String[] args)
{
    String S = "124";
    int N = 100;
     
    // Function Call
    generateCombinations(S, N);
 
    // Print required sequences
    printSequences(combinations);
}
}
 
// This code is contributed by 29AjayKumar

<script>
      // JavaScript program for the above approach
      // Store the current sequence of s
      var combination = "";
 
      // Store the all the required sequences
      var combinations = [];
 
      // Function to print all sequences of S
      // satisfying the required condition
      function printSequences(combinations) {
        // Print all Strings in the set
        for (var s of combinations) {
          document.write(s + " ");
        }
      }
 
      // Function to generate all sequences
      // of String S that are at most N
      function generateCombinations(s, n) {
        // Iterate over String s
        for (var i = 0; i < s.length; i++) {
          // Push ith character to combination
          combination += s[i];
 
          // Convert the String to number
          var x = parseInt(combination);
 
          // Check if the condition is true
          if (x <= n) {
            // Push the current String to
            // the readonly set of sequences
            combinations.push(combination);
 
            // Recursively call function
            generateCombinations(s, n);
          }
 
          // Backtrack to its previous state
          combination = combination.substring(0, combination.length - 1);
        }
      }
 
      // Driver Code
      var S = "124";
      var N = 100;
 
      // Function Call
      generateCombinations(S, N);
 
      // Print required sequences
      printSequences(combinations);
    </script>

1 11 12 14 2 21 22 24 4 41 42 44

Complejidad temporal: O(N ^N )
Espacio auxiliar: O(N ^N )