The problem Combinations Leetcode Solution provides us with two integers, n, and k. We are told to generate all the sequences that have k elements picked out of n elements from 1 to n. We return these sequences as an array. Let us go through a few examples to get a better understanding of the problem.

n = 4, k = 2

[ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]

Explanation: The output shows all the ways of picking k elements out of first n natural numbers. Here, the ordering of the numbers does not matter. Only the collection of numbers matters.

n = 1, k = 1

[[1]]

Explanation: Here, since we have a single element. We are also told to pick a single element. Thus the output is [[1]].

Table of Contents

## Approach for the Combinations Leetcode Solution

The problem Combinations Leetcode Solution asked us simply to generate all the sequences of picking k elements out of first n natural numbers. So, this is simply generating all the nCk combinations available to pick k elements. Generally, the tasks involving the generation of sequences are solved using recursion. So, we try a recursive approach to the problem. And keep track of a vector that aims to store such combinations.

So, we start with an empty vector. We push an element into it. Then recursively solve a subproblem of picking k-1 elements out of remaining n-1 elements. in this way we keep on reducing the problem until we reach the problem of picking 0 elements. When this happens, we push this temporary vector to our answer. In the end, this answer stores all the sequences of picking k elements out of n elements.

## Code for Combinations Leetcode Solution

### C++ Code

#include <bits/stdc++.h> using namespace std; void rec(int i, int k, int n, vector<int>& cur, vector<vector<int>>& res){ if(cur.size()==k) { res.push_back(cur); } else { for(int j=i;j<=n;j++) { cur.push_back(j); rec(j+1, k, n, cur, res); cur.pop_back(); } } } vector<vector<int>> combine(int n, int k) { vector<vector<int>> res; vector<int> cur; rec(1, k, n, cur, res); return res; } int main(){ vector<vector<int>> output = combine(4, 2); for(auto singleList: output){ for(auto element: singleList) cout<<element<<" "; cout<<endl; } }

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

### Java Code

import java.util.*; import java.lang.*; import java.io.*; class Main { static List<List<Integer>> res = new ArrayList<List<Integer>>(); public static void rec(int i, int k, int n, ArrayList<Integer> cur){ if(cur.size()==k) { res.add(new ArrayList(cur)); } else { for(int j=i;j<=n;j++) { cur.add(j); rec(j+1, k, n, cur); cur.remove(cur.size()-1); } } } public static List<List<Integer>> combine(int n, int k) { ArrayList<Integer> cur = new ArrayList<Integer>(); rec(1, k, n, cur); return res; } public static void main (String[] args) throws java.lang.Exception{ List<List<Integer>> res = combine(4, 2); System.out.println(res); } }

[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

## Complexity Analysis

### Time Complexity

**O(k*nCk), **here nCk means the binomial coefficient of picking k elements out of n elements.

### Space Complexity

**O(nCk), **as stated above the nCk here refers to the binomial coefficient.