Realiza todas las combinaciones de talla k

Dados dos números n y k, tienes que encontrar todas las combinaciones posibles de k números de 1…n.
Ejemplos: 
 

Input : n = 4 
        k = 2
Output : 1 2 
         1 3 
         1 4 
         2 3 
         2 4 
         3 4 

Input : n = 5 
        k = 3
Output : 1 2 3 
         1 2 4 
         1 2 5 
         1 3 4 
         1 3 5 
         1 4 5 
         2 3 4 
         2 3 5 
         2 4 5 
         3 4 5 

Hemos discutido un enfoque en la siguiente publicación.
Imprima todas las combinaciones posibles de elementos r en una array dada de tamaño n
. En esto, usamos un enfoque basado en DFS . Queremos todos los números del 1 al n. Primero empujamos todos los números de 1 a k en tmp_vector y tan pronto como k sea igual a 0, empujamos todos los números de tmp_vector a ans_vector. Después de esto, eliminamos el último elemento de tmp_vector y hacemos todas las combinaciones restantes.
 

// C++ program to print all combinations of size
// k of elements in set 1..n
#include <bits/stdc++.h>
using namespace std;
 
void makeCombiUtil(vector<vector<int> >& ans,
    vector<int>& tmp, int n, int left, int k)
{
    // Pushing this vector to a vector of vector
    if (k == 0) {
        ans.push_back(tmp);
        return;
    }
 
    // i iterates from left to n. First time
    // left will be 1
    for (int i = left; i <= n; ++i)
    {
        tmp.push_back(i);
        makeCombiUtil(ans, tmp, n, i + 1, k - 1);
 
        // Popping out last inserted element
        // from the vector
        tmp.pop_back();
    }
}
 
// Prints all combinations of size k of numbers
// from 1 to n.
vector<vector<int> > makeCombi(int n, int k)
{
    vector<vector<int> > ans;
    vector<int> tmp;
    makeCombiUtil(ans, tmp, n, 1, k);
    return ans;
}
 
// Driver code
int main()
{
    // given number
    int n = 5;
    int k = 3;
    vector<vector<int> > ans = makeCombi(n, k);
    for (int i = 0; i < ans.size(); i++) {
        for (int j = 0; j < ans[i].size(); j++) {
            cout << ans.at(i).at(j) << " ";
        }
        cout << endl;
    }
    return 0;
}

// Java program to print all combinations of size
// k of elements in set 1..n
import java.util.*;
public class Main
{
    static Vector<Vector<Integer>> ans = new Vector<Vector<Integer>>();
    static Vector<Integer> tmp = new Vector<Integer>();
       
    static void makeCombiUtil(int n, int left, int k)
    {
       
        // Pushing this vector to a vector of vector
        if (k == 0) {
            ans.add(tmp);
            for(int i = 0; i < tmp.size(); i++)
            {
                System.out.print(tmp.get(i) + " ");
            }
            System.out.println();
            return;
        }
  
        // i iterates from left to n. First time
        // left will be 1
        for (int i = left; i <= n; ++i)
        {
            tmp.add(i);
            makeCombiUtil(n, i + 1, k - 1);
  
            // Popping out last inserted element
            // from the vector
            tmp.remove(tmp.size() - 1);
        }
    }
  
    // Prints all combinations of size k of numbers
    // from 1 to n.
    static Vector<Vector<Integer>> makeCombi(int n, int k)
    {
        makeCombiUtil(n, 1, k);
        return ans;
    }
     
    public static void main(String[] args)
    {
       
        // given number
        int n = 5;
        int k = 3;
        ans = makeCombi(n, k);
    }
}
 
// This code is contributed by suresh07.

# Python3 program to print all combinations of size
# k of elements in set 1..n
ans = []
tmp = []
 
def makeCombiUtil(n, left, k):
    # Pushing this vector to a vector of vector
    if (k == 0):
        ans.append(tmp)
        for i in range(len(tmp)):
            print(tmp[i], end = " ")
        print()
        return
 
    # i iterates from left to n. First time
    # left will be 1
    for i in range(left, n + 1):
        tmp.append(i)
        makeCombiUtil(n, i + 1, k - 1)
 
        # Popping out last inserted element
        # from the vector
        tmp.pop()
 
# Prints all combinations of size k of numbers
# from 1 to n.
def makeCombi(n, k):
    makeCombiUtil(n, 1, k)
    return ans
  
# given number
n = 5
k = 3
ans = makeCombi(n, k)
 
# This code is contributed by divyeshrabadiya07.

// C# program to print all combinations of size
// k of elements in set 1..n
using System;
using System.Collections.Generic;
class GFG {
     
    static List<List<int>> ans = new List<List<int>>();
    static List<int> tmp = new List<int>();
       
    static void makeCombiUtil(int n, int left, int k)
    {
       
        // Pushing this vector to a vector of vector
        if (k == 0) {
            ans.Add(tmp);
            for(int i = 0; i < tmp.Count; i++)
            {
                Console.Write(tmp[i] + " ");
            }
            Console.WriteLine();
            return;
        }
  
        // i iterates from left to n. First time
        // left will be 1
        for (int i = left; i <= n; ++i)
        {
            tmp.Add(i);
            makeCombiUtil(n, i + 1, k - 1);
  
            // Popping out last inserted element
            // from the vector
            tmp.RemoveAt(tmp.Count - 1);
        }
    }
  
    // Prints all combinations of size k of numbers
    // from 1 to n.
    static List<List<int>> makeCombi(int n, int k)
    {
        makeCombiUtil(n, 1, k);
        return ans;
    }
 
  static void Main()
  {
     
    // given number
    int n = 5;
    int k = 3;
    ans = makeCombi(n, k);
  }
}
 
// This code is contributed by rameshtravel07.

<script>
    // Javascript program to print all combinations of size
    // k of elements in set 1..n
    let ans = [];
      let tmp = [];
         
    function makeCombiUtil(n, left, k)
    {
        // Pushing this vector to a vector of vector
        if (k == 0) {
            ans.push(tmp);
            for(let i = 0; i < tmp.length; i++)
            {
                document.write(tmp[i] + " ");
            }
            document.write("</br>");
            return;
        }
 
        // i iterates from left to n. First time
        // left will be 1
        for (let i = left; i <= n; ++i)
        {
            tmp.push(i);
            makeCombiUtil(n, i + 1, k - 1);
 
            // Popping out last inserted element
            // from the vector
            tmp.pop();
        }
    }
 
    // Prints all combinations of size k of numbers
    // from 1 to n.
    function makeCombi(n, k)
    {
        makeCombiUtil(n, 1, k);
        return ans;
    }
     
    // given number
    let n = 5;
    let k = 3;
    ans = makeCombi(n, k);
 
// This code is contributed by divyesh072019.
</script>

Producción: 
 

1 2 3 
1 2 4 
1 2 5 
1 3 4 
1 3 5 
1 4 5 
2 3 4 
2 3 5 
2 4 5 
3 4 5 

Complejidad de tiempo : O((nCk)*k), donde nCk son todos los subconjuntos posibles y k para copiar subconjuntos en ans vector.

Complejidad espacial: O((nCk)*k), para almacenar todos los subconjuntos n C k en el vector ans de tamaño k.

Este artículo es una contribución de Roshni Agarwal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.