Algorithm
Problem Name: 77. Combinations
problem Link: https://leetcode.com/problems/combinations/
Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n].
You may return the answer in any order.
Example 1:
Input: n = 4, k = 2 Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]] Explanation: There are 4 choose 2 = 6 total combinations. Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.
Example 2:
Input: n = 1, k = 1 Output: [[1]] Explanation: There is 1 choose 1 = 1 total combination.
Constraints:
1 <= n <= 201 <= k <= n
Code Examples
#1 Code Example with C Programming
Code -
C Programming
void bt(int *buff, int ***p, int *psz, int *pn, int n, int k, int d, int start) {
int i;
if (d == k) {
// all done
if (*psz == *pn) {
*psz *= 2;
*p = realloc(*p, *psz * sizeof(int *));
//assert(*p);
}
(*p)[*pn] = malloc(k * sizeof(int));
//assert((*p)[*pn]);
memcpy((*p)[(*pn) ++], buff, k * sizeof(int));
return;
}
for (i = start; i < = n; i ++) {
buff[d] = i;
bt(buff, p, psz, pn, n, k, d + 1, i + 1);
}
}
int** combine(int n, int k, int** columnSizes, int* returnSize) {
int **p, *buff;
int psz, pn;
pn = 0;
psz = 10;
p = malloc(psz * sizeof(int *));
buff = malloc(k * sizeof(int));
//assert(p && buff);
bt(buff, &p, &psz, &pn, n, k, 0, 1);
free(buff);
*columnSizes = malloc(pn * sizeof(int));
//assert(*columnSizes);
*returnSize = pn;
while (pn --) {
(*columnSizes)[pn] = k;
}
return p;
}
Input
n = 4, k = 2
Output
[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <iostream>
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
vector < vector<int> > combine(int n, int k) {
vector < vector<int> > ans;
vector<int> temp;
combineHelper(1, n, k, temp, ans);
return ans;
}
void combineHelper(int start, int end, int k, vector<int> &temp, vector < vector<int> > &ans) {
if (k == temp.size()) {
ans.push_back(temp);
return;
}
for (int i = start; i < = end; i++) {
temp.push_back(i);
combineHelper(i + 1, end, k, temp, ans);
temp.pop_back();
}
}
};
int main() {
int n = 4;
int k = 2;
Solution s;
vector < vector<int> > ans = s.combine(n, k);
for (int i = 0; i < ans.size(); i++) {
for (int j = 0; j < ans[i].size(); j++) {
printf("%d ", ans[i][j]);
}
printf("\n");
}
return 0;
}
Input
n = 1, k = 1
Output
[[1]]
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public List();
List curr = new ArrayList<>();
helper(ans, curr, new boolean[n], k, 0);
return ans;
}
private void helper(List < List curr, boolean[] visited, int k, int idx) {
if (curr.size() == k) {
ans.add(new ArrayList<>(curr));
}
else {
for (int i = idx; i < visited.length; i++) {
if (visited[i]) {
continue;
}
curr.add(i + 1);
visited[i] = true;
helper(ans, curr, visited, k, i + 1);
curr.remove(curr.size() - 1);
visited[i] = false;
}
}
}
}
Input
n = 4, k = 2
Output
[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const combine = function(n, k) {
const res = [];
bt(res, [], 1, n, k);
return res;
};
function bt(res, tmp, start, n, k) {
if (k === 0) {
res.push(tmp.slice(0));
return;
}
for (let i = start; i < = n - k + 1; i++) {
tmp.push(i);
bt(res, tmp, i + 1, n, k - 1);
tmp.pop();
}
}
Input
n = 1, k = 1
Output
[[1]]
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
bfs = [[]]
for num in range(1, n + 1):
bfs += [arr + [num] for arr in bfs if len(arr) < k]
return [arr for arr in bfs if len(arr) == k]
Input
n = 1, k = 1
Output
[[1]]
#6 Code Example with C# Programming
Code -
C# Programming
using System.Collections.Generic;
namespace LeetCode
{
public class _077_Combinations
{
public IList < IList<int>> Combine(int n, int k)
{
if (n < = 0 || k <= 0 || k > n) { return null; }
var results = new List();
for (i = 0; i < n; i++)
if (select[i]) { result.Add(i + 1); }
results.Add(result);
hasNext = false;
count = 0;
for (i = 0; i < n - 1; i++)
{
if (select[i] && !select[i + 1])
{
select[i + 1] = true;
select[i] = false;
hasNext = true;
for (j = 0; j < i; j++)
select[j] = count-- > 0 ? true : false;
break;
}
if (select[i]) { count++; }
}
if (!hasNext) break;
}
return results;
}
}
}
Input
n = 1, k = 1
Output
[[1]]