In the Leetcode 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 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 <= 20
- 1 <= k <= n
Solution in C Programming
int C(int n, int k){
if(k > 1)
return n * C(n - 1, k - 1) / k;
else
return n;
}
inline void create(int num, int n, int *ans){
int i, j;
for(i = 0, j = 0; i < n; i++){
if((num & (1 << i)) > 0)
ans[j++] = i + 1;
}
}
int** combine(int n, int k, int* returnSize, int** returnColumnSizes){
register int i, j, total = C(n, k), count = 0;
int **ans = (int**)malloc(total * sizeof(int*));
int *col = (int*)malloc(total * sizeof(int));
for(i = 0; i < total; i++){
ans[i] = (int*)calloc(k, sizeof(int));
col[i] = k;
}
*returnColumnSizes = col;
*returnSize = total;
for(i = 1; i < 1 << n; i++){
if(__builtin_popcount(i) == k){
create(i, n, ans[count]);
count++;
}
}
return ans;
}Solution in C++ Programming
class Solution {
public:
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> res;
vector<int> curr;
getComb(res,curr,1,n,k);
return res;
}
void getComb( vector<vector<int>> &res,vector<int> curr, int l, int n, int k) {
if(curr.size() == k) {
res.push_back(curr);
return;
}
for(int i=l;i<=n;i++) {
curr.push_back(i);
getComb(res,curr,i+1,n,k);
curr.pop_back();
}
}
};Solution in Java Programming
public List<List<Integer>> combine(int n, int k) {
List<Integer> nums = new ArrayList<>();
for (int i = 1; i <= n; i++) {
nums.add(i);
}
List<List<Integer>> ret = new ArrayList<>();
dfs(nums, k, 0, new ArrayList<>(), ret);
return ret;
}
private void dfs(List<Integer> nums, int k, int idx, List<Integer> path, List<List<Integer>> ret) {
if (k == 0) {
ret.add(path);
return; // backtracking
}
for (int i = idx; i < nums.size(); i++) {
List<Integer> p = new ArrayList<>(path);
p.add(nums.get(i));
dfs(nums, k-1, i+1, p, ret);
}
}Solution in Python Programming
class Solution:
def combine(self, n, k):
self.ans=[]
ds=[]
self.solve(0,n,k,ds)
return self.ans
def solve(self,idx,n,k,ds):
if len(ds)==k:
self.ans.append(ds[:])
return
for i in range(idx,n):
ds.append(i+1)
self.solve(i+1,n,k,ds)
ds.pop()
return Solution in C# Programming
public class Solution
{
private enum State
{
Initial,
Skipped,
Taken
}
public IList<IList<int>> Combine(int n, int k)
{
var result = new List<IList<int>>();
// This data represents n simple state machines. We use
// count variable to keep track of how many of those
// machines are in 'Taken' state.
var state = new State[n];
var idx = 0;
var count = 0;
while (idx >= 0)
{
if (idx == state.Length)
{
idx--;
}
else if (state[idx] == State.Initial)
{
state[idx] = State.Skipped;
idx++;
// This condition is checking if there's still enough
// unprocessed values to add up to k total values.
if (state.Length - idx < k - count)
{
idx--;
}
}
else if (state[idx] == State.Skipped)
{
state[idx] = State.Taken;
idx++;
count++;
if (count == k)
{
// Once we've got k total values save
// result and stop further propagation.
result.Add(Enumerable.Range(0, n).Where(x => state[x] == State.Taken).Select(x => x + 1).ToList());
idx--;
}
}
else // state[idx] == State.Taken
{
state[idx] = State.Initial;
count--;
idx--;
}
}
return result;
}
}Also read,