Dados dos números enteros N y K , la tarea es encontrar todas las combinaciones válidas de K números que sumen N en función de las siguientes condiciones:
- Solo se utilizan números del rango [1, 9] .
- Cada número solo se puede utilizar como máximo una vez.
Ejemplos:
Entrada: N = 7, K = 3
Salida: 1 2 4
Explicación: La única combinación posible es de los números {1, 2, 4}.Entrada: N = 9, K = 3
Salida:
1 2 6
1 3 5
2 3 4
Enfoque: La idea más simple es usar Backtracking para resolver el problema. Siga los pasos a continuación para resolver el problema:
- Si N×9 es menor que K , imprime “Imposible”
- Inicialice dos vectores <int> vis, para almacenar si un número ya se usa en la combinación o no, y subVector, para almacenar un subconjunto cuya suma sea igual a K .
- Inicialice un vector<vector<int>> , digamos salida, para almacenar todas las combinaciones posibles.
- Ahora, defina una función, digamos Recurrence(N, K, subVector, vis, output, last), para encontrar todas las combinaciones donde last representa el último número que se ha utilizado:
- Defina un caso base, si N = 0 y K = 0, luego inserte el subvector en el vector de salida .
- Ahora, si N o K es menor que 0, entonces regrese.
- Iterar sobre el rango [último, 9] usando una variable, digamos i, y empujar i en el subVector y marcar i como visitado. Ahora, llame a la función recursiva Recurrence(N-1, Ki, subVector, vis, output, last+1).
- En cada iteración del paso anterior, marque i como no visitado y extraiga i del vector subVector.
- Ahora, llame a la función recursiva Recurrence(N, K, subVector, vis, Output, 1).
- Finalmente, después de completar los pasos anteriores, imprima el vector de salida vector<int> .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Recursive function to find
// all the required combinations
void Recurrence(int N, int K,
vector<int>& sub_vector,
vector<bool>& vis,
vector<vector<int> >& output, int last)
{
// Base case
if (N == 0 && K == 0) {
// Push the current subset
// in the array output[][]
output.push_back(sub_vector);
return;
}
// If N or K is less than 0
if (N <= 0 || K <= 0)
return;
// Traverse the range [1, 9]
for (int i = last; i <= 9; i++) {
// If current number is
// not marked visited
if (!vis[i]) {
// Mark i visited
vis[i] = true;
// Push i into the vector
sub_vector.push_back(i);
// Recursive call
Recurrence(N - 1, K - i,
sub_vector, vis,
output, i + 1);
// Pop the last element
// from sub_vector
sub_vector.pop_back();
// Mark i unvisited
vis[i] = false;
}
}
}
// Function to check if required
// combination can be obtained or not
void combinationSum(int N, int K)
{
// If N * 9 is less than K
if (N * 9 < K) {
cout << "Impossible";
return;
}
// Stores if a number can
// be used or not
vector<bool> vis(10, false);
// Stores a subset of numbers
// whose sum is equal to K
vector<int> sub_vector;
// Stores list of all the
// possible combinations
vector<vector<int> > output;
// Recursive function call to
// find all combinations
Recurrence(N, K, sub_vector, vis, output, 1);
// Print the output[][] array
for (int i = 0; i < output.size(); i++) {
for (auto x : output[i])
cout << x << " ";
cout << endl;
}
return;
}
// Driver Code
int main()
{
int N = 3, K = 9;
combinationSum(N, K);
return 0;
}
Java
// Java implementation of
// the above approach
import java.util.*;
class GFG{
// Recursive function to find
// all the required combinations
static void
Recurrence(int N, int K, ArrayList<Integer> sub_vector,
boolean[] vis, ArrayList<ArrayList<Integer>> output,
int last)
{
// Base case
if (N == 0 && K == 0)
{
// Push the current subset
// in the array output[][]
output.add(new ArrayList<>(sub_vector));
return;
}
// If N or K is less than 0
if (N <= 0 || K <= 0)
return;
// Traverse the range [1, 9]
for(int i = last; i <= 9; i++)
{
// If current number is
// not marked visited
if (!vis[i])
{
// Mark i visited
vis[i] = true;
// Push i into the vector
sub_vector.add(i);
// Recursive call
Recurrence(N - 1, K - i, sub_vector, vis,
output, i + 1);
// Pop the last element
// from sub_vector
sub_vector.remove(sub_vector.size() - 1);
// Mark i unvisited
vis[i] = false;
}
}
}
// Function to check if required
// combination can be obtained or not
static void combinationSum(int N, int K)
{
// If N * 9 is less than K
if (N * 9 < K)
{
System.out.print("Impossible");
return;
}
// Stores if a number can
// be used or not
boolean[] vis = new boolean[10];
// Stores a subset of numbers
// whose sum is equal to K
ArrayList<Integer> sub_vector = new ArrayList<>();
// Stores list of all the
// possible combinations
ArrayList<ArrayList<Integer>> output = new ArrayList<>();
// Recursive function call to
// find all combinations
Recurrence(N, K, sub_vector, vis, output, 1);
// Print the output[][] array
for(int i = 0; i < output.size(); i++)
{
for(Integer x : output.get(i))
System.out.print(x + " ");
System.out.println();
}
return;
}
// Driver code
public static void main(String[] args)
{
int N = 3, K = 9;
combinationSum(N, K);
}
}
// This code is contributed by offbeat
Python3
# Python3 implementation of the above approach
output = []
vis = [False]*(10)
sub_vector = []
# Recursive function to find
# all the required combinations
def Recurrence(N, K, last):
global output, sub_vector, vis
# Base case
if (N == 0 and K == 0):
# Push the current subset
# in the array output[][]
output.append(sub_vector)
return
# If N or K is less than 0
if (N <= 0 or K <= 0):
return
# Traverse the range [1, 9]
for i in range(last, 10):
# If current number is
# not marked visited
if not vis[i]:
# Mark i visited
vis[i] = True
# Push i into the vector
sub_vector.append(i)
# Recursive call
Recurrence(N - 1, K - i, i + 1)
# Pop the last element
# from sub_vector
sub_vector.pop()
# Mark i unvisited
vis[i] = False
# Function to check if required
# combination can be obtained or not
def combinationSum(N, K):
global output, sub_vector, vis
Output = [[1, 2, 6], [1, 3, 5], [2, 3, 4]]
# If N * 9 is less than K
if (N * 9 < K):
print("Impossible")
return
# Recursive function call to
# find all combinations
Recurrence(N, K, 1)
# Print the output[][] array
for i in range(len(Output)):
for x in Output[i]:
print(x, end = " ")
print()
return
N, K = 3, 9
combinationSum(N, K)
# This code is contributed by suresh07.
C#
// C# implementation of the above approach
using System;
using System.Collections.Generic;
class GFG {
// Recursive function to find
// all the required combinations
static void Recurrence(int N, int K, List<int> sub_vector,
bool[] vis, List<List<int>> output,
int last)
{
// Base case
if (N == 0 && K == 0)
{
// Push the current subset
// in the array output[][]
output.Add(new List<int>(sub_vector));
return;
}
// If N or K is less than 0
if (N <= 0 || K <= 0)
return;
// Traverse the range [1, 9]
for(int i = last; i <= 9; i++)
{
// If current number is
// not marked visited
if (!vis[i])
{
// Mark i visited
vis[i] = true;
// Push i into the vector
sub_vector.Add(i);
// Recursive call
Recurrence(N - 1, K - i, sub_vector, vis,
output, i + 1);
// Pop the last element
// from sub_vector
sub_vector.RemoveAt(sub_vector.Count - 1);
// Mark i unvisited
vis[i] = false;
}
}
}
// Function to check if required
// combination can be obtained or not
static void combinationSum(int N, int K)
{
// If N * 9 is less than K
if (N * 9 < K)
{
Console.Write("Impossible");
return;
}
// Stores if a number can
// be used or not
bool[] vis = new bool[10];
// Stores a subset of numbers
// whose sum is equal to K
List<int> sub_vector = new List<int>();
// Stores list of all the
// possible combinations
List<List<int>> output = new List<List<int>>();
// Recursive function call to
// find all combinations
Recurrence(N, K, sub_vector, vis, output, 1);
// Print the output[][] array
for(int i = 0; i < output.Count; i++)
{
foreach(int x in output[i])
Console.Write(x + " ");
Console.WriteLine();
}
return;
}
static void Main() {
int N = 3, K = 9;
combinationSum(N, K);
}
}
// This code is contributed by divyeshrabadiya07.
Javascript
<script>
// Javascript implementation of the above approach
// Stores list of all the
// possible combinations
let output = [];
// Recursive function to find
// all the required combinations
function Recurrence(N, K, sub_vector, vis, last)
{
// Base case
if (N == 0 && K == 0)
{
// Push the current subset
// in the array output[][]
output.push(sub_vector);
// Print the output[][] array
for(let i = 0; i < sub_vector.length; i++)
{
document.write(sub_vector[i] + " ");
}
document.write("</br>");
return;
}
// If N or K is less than 0
if (N <= 0 || K <= 0)
return;
// Traverse the range [1, 9]
for(let i = last; i <= 9; i++)
{
// If current number is
// not marked visited
if (!vis[i])
{
// Mark i visited
vis[i] = true;
// Push i into the vector
sub_vector.push(i);
// Recursive call
Recurrence(N - 1, K - i, sub_vector, vis, i + 1);
// Pop the last element
// from sub_vector
sub_vector.pop();
// Mark i unvisited
vis[i] = false;
}
}
}
// Function to check if required
// combination can be obtained or not
function combinationSum(N, K)
{
// If N * 9 is less than K
if (N * 9 < K)
{
document.write("Impossible");
return;
}
// Stores if a number can
// be used or not
let vis = new Array(10);
vis.fill(false);
// Stores a subset of numbers
// whose sum is equal to K
let sub_vector = [];
// Recursive function call to
// find all combinations
Recurrence(N, K, sub_vector, vis, 1);
return;
}
let N = 3, K = 9;
combinationSum(N, K);
// This code is contributed by divyesh072019.
</script>
Producción:
1 2 6 1 3 5 2 3 4
Complejidad de Tiempo: (N*2 9 )
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por rahulagarwal14 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA