Combinations Problem Solution: 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 :
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.
Table of Contents
Combinations Problem Solution
Problem Solution In Python
def combine(self, n: int, k: int) -> List[List[int]]:
nums=[]
for i in range(1,n+1,1):
nums.append(i)
temp=[]
result=[]
def dfs(m,num):
if m==k:
result.append(temp[:])
return
else:
if len(num)<k-m:
return
for i in range(len(num)):
temp.append(num[i])
dfs(m+1,num[i+1:])
temp.pop()
dfs(0,nums)
return result
Problem Solution In Java
class Solution {
public List<List<Integer>> combine(int n, int k) {
int[] nums=new int[n];
for(int i=1;i<=n;i++)
{
nums[i-1]=i;
}
List<List<Integer>> ans=new ArrayList<>();
List<Integer> ls=new ArrayList<>();
helper(nums,k,ls,ans,0);
return ans;
}
private void helper(int[] nums,int k,List<Integer> ls,List<List<Integer>> ans,int start)
{
if(ls.size()==k)
{
ans.add(new ArrayList<>(ls));
}
else
{
for(int i=start;i<nums.length;i++)
{
ls.add(nums[i]);
helper(nums,k,ls,ans,i+1);
ls.remove(ls.size()-1);
}
}
}
}
Problem Solution In C++
class Solution {
public:
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> output;
vector<int> combination;
combine(output, combination, n, k, 1);
return output;
}
private:
void combine(vector<vector<int>>& output, vector<int> combination, int n, int k, int i) {
if (combination.size() == k) {
output.push_back(combination);
return;
}
for (int j = i; j <= n; j++) {
combination.push_back(j);
combine(output, combination, n, k, j + 1);
combination.pop_back();
}
}
};
Problem Solution In C
int Com(int n, int k) {
long int no = 1;
long int de = 1;
for (int i = 1; i < k+1; i++) {
de *= i;
}
for (int i = 0; i < k; i++) {
no *= (n-i);
}
return no / de;
}
int** combine(int n, int k, int* returnSize, int** returnColumnSizes){
int total = Com(n,k);
*returnSize = total;
int cnt = 0, j = 0;
int *K = malloc(sizeof(int) * k);
K[0] = 0;
for (int i = 1; i < k; i++) {
K[i] = K[i-1] + 1;
}
int ** res = malloc(sizeof(int *) * total);
(*returnColumnSizes) = malloc(sizeof(int) * total);
for (int i = 0; i < total; i++) {
(*returnColumnSizes)[i] = k;
res[i] = malloc(sizeof(int) * k);
for (j = 0; j < k; j++) {
res[i][j] = 1 + K[j];
}
if (i == total-1) {
break;
}
K[k-1]++;
cnt = 0;
while ((K[k-1-cnt] > n - cnt - 1) && (k - cnt != 1)) {
cnt++;
K[k-1-cnt]++;
}
for (j = cnt; j > 0; j--) {
K[k-j] = K[k-1-j] + 1;
}
}
return res;
}